问题的提出：
设计一个算法，求两个字符串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
2 #include
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
34 {
35 for (dstidx=0; dstidx+len
36 {
37 for (cnt=0; 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
52
53 return 0;
54 }
说明：13-29行是保证字符串s1的长度大于字符串s2的长度，如果strlen(s1)
关于这方面的更多的解答请参考程序员杂志的编程擂台，或者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
2 #include
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
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
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= 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] = ”;
len2 = commstr(s1,buf);
//返回较大者
return len1 > len2 ? len1 : len2;
}
int main(int arc, char *argv)
{
printf(”%d”,commstr(”shaohui”,”huishao”));
return 0;
}
不知道是否有更好的算法,我一直在找寻.
Posted in 算法(代码实现) | No Comments »
08月 15th, 2006
传言终于得到了证实，我们系要被六系合并了。。。
看了于导的space，也看了大家的留言，更加觉得伤感。这四年可以说是我们自己创业的四年，学院从无到有，每个人都付出了自己的努力。才刚刚毕业，就让我们对这样一个投入了四年青春的学院说再见，怎么舍得呢？竟然还有人对此表示高兴，不可理解。
之前一直觉得学院欠了我们很多，我们得到的太少了。或许我们真的会成为唯一的一届，但我们是不会忘记自己是软件人的，失去的东西，要靠自己来挣回来
Posted in 校园生活 | No Comments »
08月 10th, 2006
看了阎明的space才想起来，不知不觉离校已经一个月了，越来越怀念在学校的日子，自由的空间、同学、操场、图书馆。。。
已经变成了社会人，压力大了很多，而且发现要学的东西也是越来越多，社会也是个大学校，看自己能学到多少了
Posted in 工作 | No Comments »
