最长公共子字符串

求两个输入序列的最长的公共子字符串的长度。子字符串中的所有字符在源字符串中必须相邻。

 

如字符串：21232523311324和字符串312123223445，他们的最长公共子字符串为21232，长度为5。

 

输入格式：

两行，第一行为第一个字符串X，第二行为第二个字符串Y，字符串不含空格并以回车标示结束。X和Y的串长都不超过100000。

输出格式：

两行，第一行为最长的公共子字符串的长度，第二行输出一个最长的公共子字符串。

 

说明：

(1)若最长的公共子字符串有多个，请输出在源字符串X中靠左的那个。

(2)若最长公共子字符串的长度为0，请输出空串(一个回车符)。

 

如输入：

21232523311324

152341231

由于523和123都是最长的公共子字符串，但123在源串X中更靠左，因此输出：

3

123

 

分析：

最长公共子字符串必须是连续的。如果我们使用递归的方法解决的话，对于每一对字符就需要判断前面的是否已构成字串，这就会使子问题出现重复计算的问题。对于重复子问题，还是要使用动态规划的思想。

 

假设需要求的字符串为 str1 , str2 .函数 f(m,n) 求分别以str1[m] , str2[n] 结尾的公共字符串长度。

这有一下递推公式：

 

f(m,n)=0        str1[m] != str2[n] ;

f(m,n)=f(m-1,n-1) + 1      str[m]==str2[n];

 

别忘了递推的特殊边界:

f(0,n)=0;

f(m,0)=0;

 

 

 

 

代码如下：

 

#include<iostream>  
#include<string.h>  
using namespace std;  
  
int c[10000][10000];  
char str1[10000];  
char str2[10000];  
  
  
void func(int m,int n){  
      if((m<0)||(n<0)) return ;  
  
       for(int i=0;i<m;i++)  
         for(int j=0;j<n;j++) c[i][j]=0;  
  
      int besti=0,bestj=0;  
      int count=0;  
  
      for(int i=0;i<m;i++)  
          for(int j=0;j<n;j++)  
              if(str1[i]==str2[j]) {  
                  if((i==0)||(j==0)) c[i][j]=1;   //增加判断是否为第一个，第一个不能再向下  
                  else  c[i][j]=c[i-1][j-1] + 1 ;  
              }  
              else c[i][j]=0;  
  
/* 
     for(int i=0;i<m;i++){ 
         for(int j=0;j<n;j++) 
             cout<<c[i][j]<<' '; 
         cout<<endl; 
     } 

*/  
  
     for(int i=0;i<m;i++)  
         for(int j=0;j<n;j++)  
             if(c[i][j]>count) { count=c[i][j]; besti=i; bestj=j; }   //查找最长子字符串  
  
     cout<<count<<endl;  
     if(count==0) cout<<endl;  //公共子字符串长度为1，输出空行  
     else  
        for(int i=besti-count+1;i<=besti;i++) cout<<str1[i];   //否则输出靠X左边（如果多个）子字符串  
  
  
}  
  
  
int main() {  
    int m=0;  
    int n=0;  
    cin>>str1;  
    cin>>str2;  
    m=strlen(str1);  
    n=strlen(str2);  
    func(m,n);  
    return 0;  
}  

 

补充：软件开发 , C++ ,