最长公共子字符串

11077 最长公共子字符串
时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0
语言: not limited
描述
求两个输入序列的最长的公共子字符串的长度。子字符串中的所有字符在源字符串中必须相邻。
如字符串：21232523311324和字符串312123223445，他们的最长公共子字符串为21232，长度为5。
输入格式
两行，第一行为第一个字符串X，第二行为第二个字符串Y，字符串不含空格并以回车标示结束。X和Y的串长都不超过100000。
输出格式
两行，第一行为最长的公共子字符串的长度，第二行输出一个最长的公共子字符串。
说明：
(1)若最长的公共子字符串有多个，请输出在源字符串X中靠左的那个。
(2)若最长公共子字符串的长度为0，请输出空串(一个回车符)。
如输入：
21232523311324
152341231
由于523和123都是最长的公共子字符串，但123在源串X中更靠左，因此输出：
3
123
17
输入样例
21232523311324
312123223445
输出样例
5
21232

18

------------------------------------------------------

11077最长公共子字符串（动态规划）

#include<stdio.h>

#include<malloc.h>

#include<string.h>

intLCSLength(intm,intn,char*x,char*y,int**&f,int&besti,int&bestj,int&max)

{

inti,j;

for(i=0;i<m;i++){if(x[i]==y[0]){f[i][0]=1;max=f[i][0];besti=i;bestj=0;}elsef[i][0]=0;}

for(i=0;i<n;i++){if(x[0]==y[i]){f[0][i]=1;max=f[0][i];besti=0;bestj=i;}elsef[0][i]=0;}

for(i=1;i<m;i++)

for(j=1;j<n;j++){

if(x[i]==y[j]){

f[i][j]=f[i-1][j-1]+1;

if(max<f[i][j]){max=f[i][j];besti=i;bestj=j;}

}

elsef[i][j]=0;

}

return0;

}

intmain()

{

charstr1[100000],str2[100000];

intm,n,bi=0,bj=0,**c,i,max=0;

scanf("%s%s",str1,str2);

m=strlen(str1);n=strlen(str2);

c=(int**)malloc(m*sizeof(int*));

for(i=0;i<m;i++)

c[i]=(int*)malloc(n*sizeof(int));

LCSLength(m,n,str1,str2,c,bi,bj,max);

printf("%d\n",max);

for(i=bi-max+1;i<=bi;i++)

printf("%c",str1[i]);

printf("\n");

return0;

}