1 /*
 2 例如 apple peach
 3     p e a c h
 4   0 0 0 0 0 0
 5 a 0 0 0 1 1 1
 6 p 0 1 1 1 1 1
 7 p 0 1 1 1 1 1
 8 l 0 1 1 1 1 1
 9 e 0 1 2 2 2 2
10 */

11 #include<iostream>
12 #include <cstring>
13 using namespace std;
14 #define MAX 105
15 char ch1[MAX],ch2[MAX],ch[MAX];
16 int dp[MAX][MAX];
17 int max(int a,int b)
18 {
19     return a>b?a:b;
20 }
21 int main()
22 {
23     int i,j,k;
24     int m,n;
25     while(cin.getline(ch1,MAX,‘ ‘) && cin.getline(ch2,MAX,‘\n‘))
26     {
27         m = strlen(ch1);
28         n = strlen(ch2);
29         for(i=0;i<=n;i++)
30             dp[0][i] = 0;
31         for(j=0;j<=m;j++)
32             dp[j][0] = 0;
33         for(i=1;i<=m;i++)
34             for(j=1;j<=n;j++)
35                 if(ch1[i-1] == ch2[j-1])
36                     dp[i][j] = dp[i-1][j-1] + 1;
37                 else
38                     dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
39         //以上是求最长公共子序列
40         i = strlen(ch1),j = strlen(ch2);
41         k=0;
42         while(i!=0 || j!=0)        //将所求的序列保存在数组ch中，从后往前依次比较两个数组
43         {
44             if(i==0)        //说明数组ch2还有剩余元素
45             {
46                 ch[k++] = ch2[j-1];
47                 j--;
48                 continue;
49             }
50             else if(j==0)        //说明数组ch1还有剩余元素
51             {
52                 ch[k++] = ch1[i-1];
53                 i--;
54                 continue;
55             }
56             else if(ch1[i-1] != ch2[j-1])
57             {
58                 if(dp[i][j] == dp[i][j-1])
59                 {
60                     ch[k++] = ch2[j-1];
61                     j--;
62                     continue;
63                 }
64                 else if(dp[i][j] == dp[i-1][j])
65                 {
66                     ch[k++] = ch1[i-1];
67                     i--;
68                     continue;
69                 }
70             }
71             else
72             {
73                 ch[k++] = ch1[i-1];
74                 i--;j--;
75                 continue;
76             }
77         }
78         for (i=k-1;i>=0;i--)
79             cout<<ch[i];
80         cout<<endl;
81         memset(ch1,0,sizeof(ch1));
82         memset(ch2,0,sizeof(ch2));
83     }
84     return 0;
85 }