北縣縣賽 97北縣賽-2-基因序列密碼問題
作法:LIS(DP)
/*********-*********************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int
main()
{
char x[51],y[51];
while(scanf("%s %s",x,y)==2)
{
int math[51][51]={0};
int LCS[51][51][51]={0};
int a,b,c,n=strlen(x),m=strlen(y);
for(a=1;a<=n;a++)
for(b=1;b<=m;b++)
{
if(x[a-1]==y[b-1])
{
math[a][b]=math[a-1][b-1]+1;
for(c=0;c<50;c++)
LCS[a][b][c]=LCS[a-1][b-1][c];
LCS[a][b][math[a][b]]=y[b-1];
}
else
{
if(math[a-1][b]>math[a][b-1])
for(c=0;c<50;c++)
LCS[a][b][c]=LCS[a-1][b][c];
else
for(c=0;c<50;c++)
LCS[a][b][c]=LCS[a][b-1][c];
math[a][b]=(math[a][b-1]>math[a-1][b])?math[a][b-1]:math[a-1][b];
}
}
if(math[n][m]==0) printf("E\n");
else
for(a=1;a<=math[n][m];a++)
printf("%c",LCS[n][m][a]);
printf("\n");
}
return 0;
}