Chinaunix首页 | 论坛 | 博客
  • 博客访问: 968299
  • 博文数量: 214
  • 博客积分: 10173
  • 博客等级: 上将
  • 技术积分: 1867
  • 用 户 组: 普通用户
  • 注册时间: 2007-06-18 13:48
文章分类

全部博文(214)

文章存档

2012年(1)

2010年(13)

2009年(5)

2008年(98)

2007年(97)

分类: LINUX

2007-11-14 20:55:43

求公共子串问题以及其改进算法
问题的提出:
    设计一个算法,求两个字符串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
    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(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
    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)=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    {
        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;
}

不知道是否有更好的算法,我一直在找寻.
阅读(1122) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~