天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

动态规划解决最长公共子串问题

Posted on 2012-12-07 01:28 hoshelly 阅读(1183) 评论(2)  编辑 收藏 引用 所属分类: ProgrammingDS && Algorithm
设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn},要求最长公共子序列,可以按照下面方式递归计算,:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm即可得到X和Y的最长公共子序列,当xm不等于yn的时候,必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列,然后这两个里面较长者为X和Y的最长公共子序列!
首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn},当i=0或者j=0时空序列是Xi和Yj的最长公共子序列,故因此,C[i][j]=0,即有
代码如下:
 
C[i][j]=0,(i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj

最长公共子串(Longest common substring, 简称LCS)问题指的是求出给定的一组
字符串的长度最大的共有的子字符串。 
   举例说明,以下三个字符串的LCS就是 cde: 
   abcde  
   cdef  
   ccde

现在的情况是给你2个字符串,请找到他们的LCS

请注意:字符可以不相邻;

输入

输入第一行包含一个整数T,表示有T组数据;

对于每组数据包含2行,每行包含一个非空字符串,长度不超过1000个字符

输出

对于每组数据输出他们的LCS的长度,保证每组数据存在LCS;

样例输入

2
abcde
cdef
aaaaaaa
aaabaaa

样例输出
3
6

分析:
设序列X={x1,x2,x3......xm}和Y={y1,y2,y3,....yn},要求最长公共子序列,可以按照下面方式递归计算,:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm即可得到X和Y的最长公共子序列,当xm不等于yn的时候,必须解决两个子问题即找出Xm-1和Y的最长公共子序列和Yn-1和X的最长工公共子序列,然后这两个里面较长者为X和Y的最长公共子序列!
首先建立子问题的最优值递归关系。用C[i][j]表示Xi和Yj的最长公共子序列的长度。其中,Xi={x1,x2,x3......xi},Yj={y1,y2,y3,....yn},当i=0或者j=0时空序列是Xi和Yj的最长公共子序列,故因此,C[i][j]=0,即有

C[i][j]=0,(i=0,j=0)
C[i][j]=c[i-1][j-1]+1,xi=yj
C[i][j]=max(C[i][j-1],C[i-1][j]),i,j>0,xi不等于yj

实现代码如下:
#include<stdio.h>
#include<string.h>
int c[1002][1002]={0};
int main()
{
   int N,m,n,i,j;
   char x[1002],y[1002];
  scanf("%d",&N);
  while(N--)
  {
        scanf("%s",x);
        scanf("%s",y);
        m=strlen(x);
        n=strlen(y);
        for(i=1;i<=m;i++)
           for(j=1;j<=n;j++)
           {
               if(x[i-1]==y[j-1]) 
               {
                  c[i][j]=c[i-1][j-1]+1;
                 }
              else if(c[i-1][j]>=c[i][j-1])
              {
                   c[i][j]=c[i-1][j];
               }
               else
               {
                   c[i][j]=c[i][j-1];
              }
            }
          printf("%d\n",c[m][n]);
  }
  return 0;
}

参考自:http://yangchuanhuahpu.blog.163.com/blog/static/18631884020125272205862/


















Feedback

# re: 动态规划解决最长公共子串问题[未登录]  回复  更多评论   

2012-12-07 08:39 by Chipset
耗费内存太多

# re: 动态规划解决最长公共子串问题  回复  更多评论   

2012-12-07 13:06 by hoshelly
题目要求串长最多为1000,没办法。@Chipset

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理