最长公共子字符串 - c++编程基础

描述：

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

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

输入格式：

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

输出格式：

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

说明：

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

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

如输入：

21232523311324

152341231

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

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  
#include  
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;icount) { count=c[i][j]; besti=i; bestj=j; }   //查找最长子字符串  
  
     cout<>str1;  
    cin>>str2;  
    m=strlen(str1);  
    n=strlen(str2);  
    func(m,n);  
    return 0;  
}