1. #include<iostream>
2. #include<fstream>
3. #include<vector>
4. #include<queue>
5. #include<string>
6. #include<math.h>
7. using namespace std;
8. #define BIT_TOOGLE(num, index) (num) |= (1<<(index))
9. #define BIT_CLEAR(num, index) (num) &= ~(1<<(index))
10.  
11. #define BIT_SET_VALUE(num, index, bit) \
12. if(bit)\
13.         BIT_TOOGLE(num,index);\
14. else\
15.         BIT_CLEAR(num,index);
16. bool bit_check(uint8_t num, uint8_t index){
17.         uint8_t mask=pow(2,index);
18.         mask&=num;
19.         if(mask==pow(2,index))
20.         return true;
21.         else
22.         return false;
23. }
24. int main(){
25. vector<unsigned short> line, line_cur;
26. vector<vector<uint8_t > >par;
27. string x,y;
28.  
29. getline(cin, x);
30. getline(cin, y);
31.  
32. uint8_t siz;
33. if((y.size())%4==0)
34. siz=(y.size())/4;
35. else
36. siz=(y.size())/4+1;
37. vector<uint8_t> temp2(siz,0);
38. vector<char> ans;
39.  
40. for(unsigned short i=0;i<=x.size();++i)
41.         par.push_back(temp2);
42.        
43. unsigned short m=x.size();
44. unsigned short n=y.size();
45. unsigned short cur;
46.  
47. for(unsigned short i=0;i<n+1;++i)
48.         line.push_back(0);
49.         unsigned short prev=0;
50.    for(unsigned short i=1;i<m+1;++i){
51.         line_cur.push_back(0);
52.      for(unsigned short j=1;j<n+1;++j){
53.        if(x[i-1]==y[j-1]){
54.          cur=line[j-1]+1;
55.          BIT_SET_VALUE(par[i][j],2*j%4,1);
56.          }
57.        else{
58.          if(line[j]>=prev){
59.            cur=line[j];
60.            par[i][j]=2;
61.            BIT_SET_VALUE(par[i][j],2*j%4+1,1);
62.            }
63.          else{
64.            cur=prev;
65.            BIT_SET_VALUE(par[i][j],2*j%4,1);
66.            BIT_SET_VALUE(par[i][j],2*j%4+1,1);
67.            }
68.            }
69.     prev=cur;
70.     line_cur.push_back(cur);
71.     }
72.     line=line_cur;
73.     prev=0;
74.     line_cur.clear();
75.     }
76. while(true){
77.         if(m==0||n==0)
78.         break;
79.         if(bit_check(par[m][n],2*n%4)&&!bit_check(par[m][n],2*n%4+1)){
80.                 --m;
81.                 --n;
82.                 ans.push_back(x[m]);
83.         }
84.         else{
85.                 if(!bit_check(par[m][n],2*n%4)&&bit_check(par[m][n],2*n%4+1))
86.                         --m;
87.                 else
88.                         --n;
89.         }
90. }
91. for(int i=ans.size()-1;i>=0;i--){
92. cout<<ans[i];
93. }
94. cout<<endl;
95. }