关于这方面的更多的解答请参考程序员杂志的编程擂台，或者1998年的程序员考试的下午试题第一题．
时间复杂度分析:
假设s1的长度为n,s2的长度为m, 按照最坏的打算，假设不能够找到公共子串（也就是公共子串的长度为0)
进行的比较次数为(也就是第38行代码的执行次数)
为了便于计算我们假设n=m
利用高中的数列求和的知识,很容易得到,则原时间复杂度为O(n4)
2.我的改进算法
原来的求解方法的时间复杂度为O(n4),实际上还有比较大的改进余地,原来的问题完全可以在O(n*m)的时间内得到求解.
仔细分析原来的求解的过程，对于子串s2的任意一个长度k,字符串s1和s2中的任意两个字符之间都要进行一次比较,而当k减少1的时候,s1和s2中的任意两个字符又要进行比较一次,这显然是冗余的.故如果利用以前的比较结果,时间复杂度可以降低到O(n3).
下面具体说说我的改进算法
将字符串s1和s2分别写在两把直尺上面(我依然用s1,s2来表示这两把直尺),然后将s1固定,s2的尾部和s1的头部对齐,然后逐渐移动直尺s2,比较重叠部分的字符串中的公共子串的长度,直到直尺s2移动到s1的尾部.在这个过程中求得的最大长度就是s1,s2最大子串的长度.
下图是求解过程的图示,蓝色部分表示重叠的字符串,红色的部分表示重叠部分相同的子串
其中s1="shaohui",s2="ahui",最后的求得的结果为3
按照这个思想，很容易得到这个例子程序
1 #include <iostream>
2 #include <string.h>
3 using namespace std;
4 int commstr(char *s1, char *s2)
5 {
6 int len1 = strlen(s1),len2 = strlen(s2),len = len1 + len2;
7 int cnt,s1start,s2start,idx,max = 0,curmax;
8
9 for (cnt=0; cnt
10 {
11 s1start = s2start = 0;
12 if (cnt < len1)
13 s1start = len1 - cnt;
14 else
15 s2start = cnt - len1;
16
17 curmax = 0;
18 for (idx=0; (s1start+idx
19 {
20 if (s1[s1start+idx] == s2[s2start+idx])
21 curmax++;
22 else
23 {
24 max = curmax > max ? curmax : max;
25 curmax = 0;
26 }
27 }
28 max = curmax > max ? curmax : max;
29 }
30
31 return max;
32 }
33 int main(int argc, char **argv)
34 {
35 if (argc < 3)
36 return 0;
37 printf("%s\t%s:%d",argv[1],argv[2],commstr(argv[1],argv[2]));
38 return 0;
39 }
时间复杂度分析:
容易计算,时间复杂度O(n,m)=(n+m)m
令n=m
则时间复杂度O(n)=n2,与以前的算法相比较,降低了2次,应该算是比较大的改进了
3.递归的方法
我用Python写了一个递归的求解方法，如下
def commstr(long,short) :
if short in long :
return len(short)
return max(commstr(long,short[:-1]),commstr(long,short[1:]))
print commstr('shaohui','huishao')
代码很简单，原理也很简单，尽管是使用的递归，但是基本思想还是以前的求解方法：对于字符串a,b,尽量用b的最大的子字符串c去匹配另外一个字符串a，如果c不是a的子串，那么用字符串b的长度比b少1的子串去匹配a,直到匹配到了为止或者子串的长度为0．
为了便于参考，我也用C写了个，不用解释了，因为注释已经很清楚了
#include
#include
#define BUFFER_SIZE 255
int commstr(char *s1, char *s2)
{
char buf[BUFFER_SIZE];
int start,cnt=-1,len1=strlen(s1),len2=strlen(s2);
for (start=0; start+len2 {
for (cnt=0; cnt if (s1[start+cnt] != s2[cnt])
break;
if (cnt >= len2)//如果在s1中找到一个字串和s1相同
break;
}
if (cnt >= len2)//如果s2是s1的子串
return len2;
//把s2中后len2-1个字符构成的串同s1比较,并求字串长度
len1 = commstr(s1,s2+1);
//把s2中前len2-1个字符构成的串同s1比较,并求字串长度
strncpy(buf,s2,len2-1);
buf[len2-1] = '\0';
len2 = commstr(s1,buf);
//返回较大者
return len1 > len2 ? len1 : len2;
}
int main(int arc, char *argv)
{
printf("%d",commstr("shaohui","huishao"));
return 0;
}
不知道是否有更好的算法,我一直在找寻.
