讨论 / 记忆化搜索AC
K3258A 2012-09-09 03:17:00
点我顶贴 收藏 删除
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

char a[1000+10],b[1000+10];

int F[1000+10][1000+10];

int find(int i,int j)

{ int x=0,y,z;

if (i<0||j<0) return 0;

if (F[i][j]!=-1) return F[i][j];

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

x=find(i-1,j-1)+1;

return F[i][j]=x;

}

int main()

{ int i,j,an,bn,maxl=0,maxa;

memset(F,-1,sizeof(F));

scanf("%s%s",a,b);

an=strlen(a);

bn=strlen(b);

for (i=an-1;i>=0;i--)

for (j=bn-1;j>=0;j--)

{ if (maxl<=find(i,j))

{ maxl=find(i,j);

maxa=i;

}

}

for (i=maxa-maxl+1;i<=maxa;i++)

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

putchar(10);

return 0;

}

庆祝AC第一题

查看更多回复
提交回复