1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <cstring> 5 using namespace std; 6 char s1[105][35],s2[105][35],s[105][35]; 7 int mark[105][105],dp[105][105],cnt; 8 int l1,l2; 9 void LCS(){10     memset(mark,0,sizeof(mark));11     memset(dp,0,sizeof(dp));12     for(int i=0;i<=l1;i++){13         mark[i][0]=1;14     }15     for(int i=0;i<=l2;i++){16         mark[0][i]=-1;17     }18     for(int i=0;i<l1;i++){19         for(int j=0;j<l2;j++){20             if(!strcmp(s1[i],s2[j])){21                 dp[i+1][j+1]=dp[i][j]+1;　　　　　　22                 mark[i+1][j+1]=0;　　　　　　　　　　//0向左上找23             }24             else if(dp[i][j+1]>=dp[i+1][j]){25                 dp[i+1][j+1]=dp[i][j+1];26                 mark[i+1][j+1]=1;           //1向上找27             }28             else {29                 dp[i+1][j+1]=dp[i+1][j];30                 mark[i+1][j+1]=-1;　　　　　　//-1向左找31             }32         }33     }34 }35 void gets(int i,int j){　　　　　　　　　　//递归从右下递归到左上36     if(!i&&!j)return ;37     if(mark[i][j]==0)38     {39         gets(i-1,j-1);40         strcpy(s[cnt++],s1[i-1]);41     }42     else if(mark[i][j]==1)43     {44         gets(i-1,j);45     }46     else47     {48         gets(i,j-1);49     }50 }51 int main(){52     //freopen("test.txt","r",stdin);53     while(~scanf("%s",s1[0])){54         int i;55         for(i=1;i<101;i++){56             scanf("%s ",s1[i]);57             if(!strcmp(s1[i],"#"))break;58         }59         l1=i;60         for(i=0;i<101;i++){61             scanf("%s",s2[i]);62             if(!strcmp(s2[i],"#"))break;63         }64         l2=i;65         LCS();66         cnt = 0;67         gets(l1,l2);68         printf("%s",s[0]);69         for(i = 1; i<cnt; i++)70         {71             printf(" %s",s[i]);72         }73         printf("\n");74     }75     return 0;76 }