LCS算法:微软面试题Review

当年微软面试时要求我写一个返回两个任意字串中最大公共串的函数，即abcdef 和 qcfbcc 返回值为bc语言不限

我的思路：
1.确定一个串为长串，另一个串为短串，在长串中找短串(长串中最长的公串可能性就是短串本身)
2.顺序确定短串中的每个字符是否在长串中出现(先做一个预定位)
3.如满足条件2，即短串中某个字符在长串中出现，在长串中试图找从这个字符起到短串末尾止的整个串
4.如果不满足条件3，短串末尾递减1个字符，直到找到此次字符出现的最大长度(至少是一个字符)
5.把此次找到的字符长度，与临时变量比较，如果此次长度大于历史长度，重赋值返回值
6.重复2-5，直到短串末尾

我的实现：
C#版
public static string GetPubMaxString(string Value1,string Value2)
{
string result=null,stmp;
int maxLen=0;
if (Value2.Length>Value1.Length)//确保Value1是长串
{
stmp=Value1;
Value1=Value2;
Value2=stmp;
}
for (int i=0;i<Value2.Length;i++)
{
if (Value1.IndexOf(Value2[i])>-1)//长串中依次判断短串的每个字符是否出现
{
stmp=Value2.Substring(i);//截取短串中出现字符到末尾存入变量
for (int ii=stmp.Length;ii>0;ii--)
{
if (Value1.IndexOf(stmp.Substring(0,ii))>-1)//长串中依次判断短串变量的左取子串是否出现
if (ii>maxLen) //如果出现并且此串长度大于上串的长度
{
result=stmp.Substring(0,ii);
maxLen=ii;
}
}
}
}
return result;
}

此算法的缺点是需要用很多次Substring方法,而此方式是需要创建新的string对象的,所以系统资源消耗比较大

后来在CSDN上看到了soholi(天涯孤棹) 网友实现上更简洁的算法：
public static string GetLargePublicString(string A,string B)
{
string shortString = A.Length > B.Length ? B : A;//取较短者;
string longString = A.Length > B.Length ? A : B;//取较长者;
for (int i = shortString.Length; i > 0; i--)//长度递减
{
for (int j = 0; j <= shortString.Length - i; j++)//位置递增
{
if (longString.IndexOf(shortString.Substring(j,i)) != -1)
{
return shortString.Substring(j, i);
}
}
}
return string.Empty;
}

真是可以算是很优雅简洁的实现，两个实现主要区别就在于，我那个GetPubMaxString是先定位确实存在的一个字符后，才开始找这个一定存 在，但长度未知的公共串，而网友soholi(天涯孤棹) 的GetLargePublicString则是在长串遍历整个短串的组合。
最近和薛 强兄吃饭聊起来，他给出了LCS(Longest Common Subsequence)算法的正解。其实早有牛人针对这一问题给出了标准算法了，一试之下，确实还是性能最好的方式。完全不需要用.net String对象所消耗的开销，而是语言无关的传统数组比较的方式，在其他语言也有借鉴意义，看来这也是传统的C、C++具有顽强生命力的原因所在之一 吧，算法的魅力与力量确实还是博大精深啊！

算法如下：

public static string Compare(string str1, string str2)
{
if (str1.Length < str2.Length)
{
string strTemp = str1;
str1 = str2;
str2 = strTemp;
}

int[] sign = new int[str1.Length];
int length = 0;
int end = 0;
for (int i = 0; i < str2.Length; i++)
{
for (int j = str1.Length - 1; j >= 0; j-- )
{

if (str2[i] == str1[j])
{
if (i == 0 || j == 0)
sign[j] = 1;
else
sign[j] = sign[j - 1] + 1;
}
else
sign[j] = 0;

if (sign[j] > length)
{
length = sign[j];
end = j;
}
}
}
return str1.Substring(end - length + 1, length);
}