求公共子串问题以及其改进算法
求公共子串问题以及其改进算法
问题的提出：
设计一个算法，求两个字符串s1,s2的最长公共子字符串的长度．例如字符串"shaohui","huishao"的最长公共子字符串为"shao",因此，结果为4.
最早看到这个问题，大约是２年前在CSDN程序员杂志的编程擂台上面，后来又在程序员考试的题目当中遇到，但是他们所使用的方法都需要消耗比较多的时间，这里我先简单说明一下这个问题的原始的解答方法，然后再介绍我的改进算法．
1.以前的算法
算法思想：对于两个字符串s1,s2(假设字符串s1长度大于字符串s2的长度),设的长度为m,那么s2的子串可以按照其长度分成m类
假设s1="shaohui",s2="ahui"，则s2的子串可以分成以下几类
4:ahui
3:ahu,hui
2:ah,hu,ui
1:a,h,u,i
然后按照长度从大到小去匹配s1,如果某个子串也是s1的子串，则找到问题的答案了．
这是我用C写的例子程序，可以作为参考
1 #include <iostream>
2 #include <cstring>
3 using namespace std;
4 /*
5 * Get the length of common substring of s1 and s2
6 * if there is no common substring between s1 and s2, return 0
7 */
8 int commstr(char *s1, char *s2)
9 {
10 char *src,*dst;
11 int len,len1,len2,cnt,srcidx,dstidx,srcbeg,dstbeg;
12
13 len1 = strlen(s1);
14 len2 = strlen(s2);
15 //assure that the length of src is large then dest
16 if (len1 > len2)
17 {
18 src = s2;
19 dst = s1;
20 len = len1;
21 len1 = len2;
22 len2 = len;
23 }
24 else
25 {
26 src = s1;
27 dst = s2;
28 }
29
30 len = len1;
31 while (len > 0)
32 {
33 for (srcidx=0; srcidx+len<=len1; srcidx++)
34 {
35 for (dstidx=0; dstidx+len<=len2; dstidx++)
36 {
37 for (cnt=0; cnt<len; cnt++)
38 if (src[srcidx+cnt] != dst[dstidx+cnt])
39 break;
40 if (cnt >= len)//common string is found
41 goto found;
42 }
43 }
44 len --;
45 }
46 found: return len;
47 }
48 int main(int argc, char **argv)
49 {
50 if (argc >= 3)
51 cout<<commstr(argv[1],argv[2]);
52
53 return 0;
54 }
说明：13-29行是保证字符串s1的长度大于字符串s2的长度，如果strlen(s1)<strlen(s2),那么就把s1和s2交换,算法真正的实现部分是30-45行．
关于这方面的更多的解答请参考程序员杂志的编程擂台，或者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<len; 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<len1) && (s2start+idx<len2); 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 <stdio.h>
#include <string.h>
#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<len1; start++)
{
for (cnt=0; cnt<len2; 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;
}
不知道是否有更好的算法,我一直在找寻.
