1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int dp[1001][1001];
 5 int f[1001][1001];
 6 char a[1000],b[1000];
 7 int l1,l2;
 8 int Length(char a[])    //返回一字符串长度 
 9 {
10     int i;
11     for(i=0;a[i]!=‘\0‘;i++);
12     return i;
13 }
14 void lcs_pre(char a[],char b[])    //进行标记 
15 {
16     l1 = Length(a);
17     l2 = Length(b);
18     for(int i=0;i<=l1;i++){
19         dp[i][0] = 0;
20         f[i][0] = 3;
21     }
22     for(int i=0;i<=l2;i++){
23         dp[0][i] = 0;
24         f[0][i] = 1;
25     }
26     for(int i=1;i<=l1;i++)
27         for(int j=1;j<=l2;j++){
28             if( a[i-1]==b[j-1] ){
29                 dp[i][j] = dp[i-1][j-1] + 1;
30                 f[i][j] = 2;
31             }
32             else if( dp[i][j-1]>=dp[i-1][j] ){
33                 dp[i][j] = dp[i][j-1];
34                 f[i][j] = 1; 
35             }
36             else{
37                 dp[i][j] = dp[i-1][j];
38                 f[i][j] = 3;
39             }
40         }
41 }
42 void Print(int x,int y)    //输出结果字符串 
43 {
44     if(x==0 && y==0)
45         return ;
46     switch(f[x][y]){
47         case 1:
48             Print(x,y-1);
49             cout<<b[y-1];
50             break;
51         case 2:
52             Print(x-1,y-1);
53             cout<<a[x-1];
54             break;
55         case 3:
56             Print(x-1,y);
57             cout<<a[x-1];
58             break;
59         default:break;
60     }
61     return ;
62 }
63 int main()
64 {
65     while(cin>>a>>b){ 
66         l1 = Length(a);
67         l2 = Length(b);
68         lcs_pre(a,b);    //进行标记
69         Print(l1,l2);
70         cout<<endl;
71     }
72     return 0;
73 }