1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 100 + 5;17 18 char s1[maxn],s2[maxn];19 int d[maxn][maxn];20 int mark[maxn][maxn];21 22 void LCS(int n, int m)23 {24     memset(d,0,sizeof(d));25     for(int i = 1;i<=n;i++)26     mark[i][0] = 2;27     for(int i = 1;i<=m;i++)28     mark[0][i] = 3;29 30     for(int i=1;i<=n;i++)31     {32         for(int j=1;j<=m;j++)33         {34             if(s1[i]==s2[j])35             {36                 d[i][j]=d[i-1][j-1]+1;37                 mark[i][j]=1;38             }39             else40             {41                 if(d[i-1][j]>d[i][j-1])42                 {43                     d[i][j]=d[i-1][j];44                     mark[i][j]=2;45                 }46                 else47                 {48                     d[i][j]=d[i][j-1];49                     mark[i][j]=3;50                 }51             }52         }53     }54 }55 56 void print(int i,int j)57 {58     if(i==0 && j==0)  return;59     if(mark[i][j]==1)60     {61         print(i-1,j-1);62         printf("%c",s1[i]);63     }64     else if(mark[i][j]==2)65     {66         print(i-1,j);67         printf("%c",s1[i]);68     }69     else70     {71         print(i,j-1);72         printf("%c",s2[j]);73     }74 }75 76 int main()77 {78     //freopen("in.txt","r",stdin);79     while(~scanf("%s%s",s1+1,s2+1))80     {81         int len1=strlen(s1+1);82         int len2=strlen(s2+1);83 84         LCS(len1,len2);85         print(len1,len2);86         printf("\n");87     }88     return 0;89 }