本文共 884 字，大约阅读时间需要 2 分钟。

最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

这个问题，不妨设第一个串为a，长度为n，第二个串为b，长度m。那么最长的子序列长度为f（n,m）

当a[n]=a[m]时

f(n,m)=1+f(n-1,m-1)

否则f(n,m)=max(f(n-1),f(m-1))

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #define maxn 5+5*10e+5using namespace std;#define N 256int f(const char* s1, const char* s2){	int a[N][N];	int len1 = strlen(s1);	int len2 = strlen(s2);	int i,j;	memset(a,0,sizeof(int)*N*N);	int max = 0;	for(i=1; i<=len1; i++)    {		for(j=1; j<=len2; j++)		{			if(s1[i-1]==s2[j-1])			{				a[i][j] = a[i-1][j-1]+1;  //填空				//if(a[i][j] > max)				//max = a[i][j];//直接return max			}			else            {                a[i][j]=a[i-1][j]>a[i][j-1]?a[i-1][j]:a[i][j-1];            }		}	}	return a[len1][len2];}int main(){	printf("%d\n", f("abcdkkk", "baabcdadabc"));	return 0;}
       
      
     
    
   

转载地址：http://phfai.baihongyu.com/