求公共子串题以及其改进算法.doc

《求公共子串题以及其改进算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求公共子串问题以及其改进算法问题的提出：设计一个算法，求两个字符串s1,s2的最长公共子字符串的长度．例如字符串"shaohui","huishao"的最长公共子字符串为"shao",因此，结果为4.最早看到这个问题，大约是２年前在CSDN程序员杂志的编程擂台上面，后来又在程序员考试的题目当中遇到，但是他们所使用的方法都需要消耗比较多的时间，这里我先简单说明一下这个问题的原始的解答方法，然后再介绍我的改进算法．　1.以前的算法算法思想：对于两个字符串s1,s2(假设字符串s1长度大于字符串s2的长度),设的长度为m,那么s2的子串可以按照其长度分成m类假设s1="shaohui"

2、,s2="ahui"，则s2的子串可以分成以下几类4:ahui3:ahu,hui2:ah,hu,ui1:a,h,u,i然后按照长度从大到小去匹配s1,如果某个子串也是s1的子串，则找到问题的答案了．这是我用C写的例子程序，可以作为参考1#include2#include3usingnamespacestd;4/*5*Getthelengthofcommonsubstringofs1ands26*ifthereisnocommonsubstringbetweens1ands2,return07*/8intcommstr(char*s1,char

3、*s2)9{10char*src,*dst;11intlen,len1,len2,cnt,srcidx,dstidx,srcbeg,dstbeg;1213len1=strlen(s1);14len2=strlen(s2);15//assurethatthelengthofsrcislargethendest16if(len1>len2)17{18src=s2;19dst=s1;20len=len1;21len1=len2;22len2=len;23}24else25{26src=s1;27dst=s2;28}2930len=len1;31while(len>0)32{33for(

4、srcidx=0;srcidx+len<=len1;srcidx++)34{35for(dstidx=0;dstidx+len<=len2;dstidx++)36{37for(cnt=0;cnt=len)//commonstringisfound41gotofound;42}43}44len--;45}46found:returnlen;47}48intmain(intargc,char**argv)49{50if(argc>=3)51cout<

5、ommstr(argv[1],argv[2]);5253return0;54}说明：13-29行是保证字符串s1的长度大于字符串s2的长度，如果strlen(s1)

6、度为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,比较重叠部分的字符串

7、中的公共子串的长度,直到直尺s2移动到s1的尾部.在这个过程中求得的最大长度就是s1,s2最大子串的长度.下图是求解过程的图示,蓝色部分表示重叠的字符串,红色的部分表示重叠部分相同的子串其中s1="shaohui",s2="ahui",最后的求得的结果为3按照这个思想，很容易得到这个例子程序1#include2#include3usingnamespacestd;4intcommstr(char*s1,char*s2)5{6intlen1=