最长连续公共子串，我参照了多方权威说法多次实验才做出这样的代码，居然只过1个点，问题在哪里？

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

char a[1002],b[1002],l,h,na,nb；

void find()

{

int i,j,k,t,tt；

int **m；

char re[1001]；

m=(int **)malloc(1002*sizeof(int *))；

for(i=0；i<1002；i++)

m[i]=(int *)malloc(1002*sizeof(int))；

na=strlen(a)；

nb=strlen(b)；

for(i=0；i<=1000；i++)

for(j=0；j<=1000；j++)

m[i][j]=0；

for(i=1；i<=na；i++)

for(j=1；j<=nb；j++)

{

if(a[i-1]==b[j-1])

m[i][j]=m[i-1][j-1]+1；

else

m[i][j]=0；

}

k=t=tt=0；

for(i=1；i<=na；i++)

for(j=1；j<=nb；j++)

if(m[i][j]>k)

k=m[i][j],t=i,tt=j；

re[k]=’\0’；

printf("%d",k)；

k--；

while(t!=0 && tt!=0)

{

if(a[t-1]!=b[tt-1])

break；

re[k]=a[t-1]；

k--；

t--；

tt--；

}

printf("%s",re)；

}

int main()

{

scanf("%s\n",a)；

scanf("%s\n",b)；

find()；

}

这题其实不必那么麻烦的。。

最简单的方法，就是枚举A串的起始位置i和B串的起始位置j；记当前已经找到的最长子串为ans；

1.若A[i+ans]!=B[j+ans]，那么跳过，j++；否则转2

2.A[i+ans]==B[j+ans]，那么开始令ti=i,tj=j从A[ti]，B[tj]开始判断，一直到A[ti]!=B[tj]，若此时ti-i+1>ans,那么就用ans=ti-i+1, 然后把A[i]-A[ti]复制到char c[].

这样是最朴素的算法了，若要考虑更优的算法的话，建议去看看KMP算法。可以在线性时间解决。。

下面是我的一段代码。。

for(int i=0；i<l1；i++){

for(int j=0；j<l2；j++){

if(a[i]==b[j]){

if(a[i+ans]!=b[j+ans]&&i+ans<l1&&j+ans<l2)

continue；

if(a[i+ans]==b[j+ans]&&i+ans<l1&&j+ans<l2){

int k=0,aa=i,bb=j；

while(a[aa]==b[bb]){

tc[k]=a[aa]；

aa++,bb++；

k++；

}

if(k>ans){

ans=k；

for(int i=0；i<k；i++)

c[i]=tc[i]；

}

}

}

}

}

你理解错题意了，最长公共子串，没有连续性。完全用不到动归，最多是个枚举+相加……

[quote][url=/Redirect.asp?Act=Reply&DID=2004&RID=7065]原帖[/url]由 [i]cc[/i] 于 2008-10-20 20:44:00 发表

你理解错题意了，最长公共子串，没有连续性。完全用不到动归，最多是个枚举+相加……[/quote]

不对呀？

题目中说是连续的了……