2009-06-28 19:09:13來源不明

北縣縣賽 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;
}