SZSM面试题:写一个可以返回任意两个string串的最大公串的函数

Question

可以写实例函数出来,也可以说说算法思路
我当时写了一个,但认为应该还有更优解

Answer 1

我的实现：
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;
}

Answer 2

感兴趣：
首先确定两个字符串的长度，长度分别为m 和n
假设我们m >= n
那么需要比较的最低次数为：  1+2+3+...+n次

Answer 3

刚才写错了个字感兴趣：
首先确定两个字符串的长度，长度分别为m 和n
假设我们m >= n
那么需要比较的最多比较次数为：  1+2+3+...+n次，最少比较次数为1

Answer 4

楼主的算法可能比我想的高效,我也写一下,就当是抛砖引玉吧不涉及语言,只是思想开始比较时:
第一步
aaaaa
    bbbbbbbbbbbbbbbbbbb第二步
 aaaaa
    bbbbbbbbbbbbbbbbbbb
......第X步                  aaaaa
    bbbbbbbbbbbbbbbbbbb最后一步
                      aaaaa
    bbbbbbbbbbbbbbbbbbb
只比较相个字符串重叠的部分,重叠部分要全部比较,不管中间有没有不相等的,也就是取重叠部分中最大公共字符串
在第 X 步和 最后一步之间的比较不是必需的,如果重叠部份已经小于已知MAX_LEN,则可中止比较了aaa 和bbb 长短无所谓感觉,楼主的算法比我的效率要高

Answer 5

呵呵,CSDN的字符串排列有问题...
第一步是只有一个字符串重叠
第X步是aaa的最后一个字符串和bbb的最后一个字符串重叠

Answer 6

在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则是在长串遍历整个短串的组合，这两者比较起来，也算是一个时间有优势，一个空间有优势的差别吧，不知大家还有没有更让人有启发的实现