分享
 
 
 

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

王朝other·作者佚名  2006-06-12
窄屏简体版  字體: |||超大  

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

问题的提出:

设计一个算法,求两个字符串s1,s2的最长公共子字符串的长度.例如字符串"shaohui","huishao"的最长公共子字符串为"shao",因此,结果为4.

最早看到这个问题,大约是2年前在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;

}

不知道是否有更好的算法,我一直在找寻.

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有