摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: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;
}