竹子听

4月2日 Plan 2

呼.....原来是这样的......最长公共子串

子串：连续的

子序列：非连续的

我就说为什么我看了这么久的标算，还纳闷怎么能这么写呢？？

果然是理解错了

这应十分应景的响起“若果标算太难请坚定信念，不如回头再看一眼题面”

唉果然是我太弱了Orz

构造一个二维矩阵，对角线求最长就ok了

***注意滚动数组要倒过来的啊，怎么太久没写动规了这都忘了

#include<cstdio>

#include<cstring>

#define maxn 1001

#define max(x,y) x>y?x:y

#define min(x,y) x<y?x:y

int n,m,a[maxn],b[maxn],t[maxn],ans=0;

void clear()

{

memset(t,0,sizeof(int));

memset(a,0,sizeof(int));

memset(b,0,sizeof(int));

}

int main()

{

clear();

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=1;i<=m;i++) scanf("%d",&b[i]);

for(int i=1;i<=n;i++)

  for(int j=m;j>=1;j--)

 {

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

else t[j]=0;

ans=max(ans,t[j]);

 }

printf("%d",ans);

}