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

问题的提出：

    设计一个算法，求两个字符串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

    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)

关于这方面的更多的解答请参考程序员杂志的编程擂台，或者1998年的程序员考试的下午试题第一题．

　

时间复杂度分析:

    假设s1的长度为n,s2的长度为m,　按照最坏的打算，假设不能够找到公共子串（也就是公共子串的长度为0)

进行的比较次数为(也就是第38行代码的执行次数)

为了便于计算我们假设n=m

利用高中的数列求和的知识,很容易得到,则原时间复杂度为O(n⁴)

　

2.我的改进算法

    原来的求解方法的时间复杂度为O(n⁴),实际上还有比较大的改进余地,原来的问题完全可以在O(n*m)的时间内得到求解.

    仔细分析原来的求解的过程，对于子串s2的任意一个长度k,字符串s1和s2中的任意两个字符之间都要进行一次比较,而当k减少1的时候,s1和s2中的任意两个字符又要进行比较一次,这显然是冗余的.故如果利用以前的比较结果,时间复杂度可以降低到O(n³).

    下面具体说说我的改进算法

    将字符串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)=n^2,与以前的算法相比较,降低了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;
}

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

阅读(249) | 评论(0) | 转发(0) |

0

上一篇：函数指针与软件设计

下一篇：在CPP中调用Jscript中的函数