#include <bits/stdc++.h>
#define pi pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,a,b) for(int i = a ; i <= b;i++)
using namespace std;
void debug(int x){
    cerr<<x<<endl;
}
void debug(vector<int> v){
    for(int i = 0 ; i<v.size(); i++) cerr<<v[i]<<" ";
    cerr<<"\n";
}
void debug(int *A, int N){
    for(int i = 0 ; i < N;i++) cerr<<A[i]<<" ";
    cerr<<endl;
}
void debug(int *A, int i, int j){
    for(int k = i;k<=j;k++) cerr<<A[k]<<" ";
    cerr<<endl;
}
void scan(vector<int> &h,int N){
    for(int i = 0 ; i < N;i++){
        scanf("%d",&h[i]);
    }
}










int lcs[3001][3001] = {0};
int path[3001][3001] = {-1}; //1 include current , 2 came from left, 3 came from top
string s,t;
int N,M;
void initialize(){
                  lcs[0][0] = 0; path[0][0] = 2;
                  if(s[0] == t[0]) { lcs[0][0] = 1; path[0][0] = 1; //we must include it 
                  }
                            //traverse the first column
                  for(int j = 1 ; j < M; j++){
                           //if previous value was one current will also be 1
                           if(lcs[0][j-1] == 1) {
                                      lcs[0][j] = 1;  path[0][j] = 2; //go left from here
                            }
                           else{
                                      lcs[0][j] = 0;
                                      if(t[j] == s[0]){
                                       lcs[0][j] = 1;  path[0][j] = 1; //include it and go to top
                                       }
                                      else path[0][j] = 2; //came from left ..so skip it
                               }
                        }
                         //similar lines..as previous one
                for(int i = 1 ; i < N ; i++){
                         if(lcs[i-1][0] ==1){ path[i][0] = 3; lcs[i][0] = 1;}
                         else {
                                lcs[i][0] = 0;
                                if(s[i]==t[0]){
                                   lcs[i][0]=1; path[i][0] = 1; //include it
                                 }  
                                else path[i][0] = 3; //came from top
                             }
                         }
}
int main(){
    cin>>s>>t;
    //dp[i][j] is the solution for si and tj
   N = s.length(); 
   M = t.length();
    //initialization of the dp array
    initialize();
    //intialization ends ...........
    for(int i = 1; i < N; i++){
        for(int j = 1;  j <  M ; j++){
             if(s[i] == t[j]){
                  lcs[i][j] = lcs[i-1][j-1] + 1; path[i][j]= 1; //include current
              }
            else{
                int t = lcs[i-1][j]; //top
                int l = lcs[i][j-1]; //left
                if(t>l){
                    path[i][j] = 3;
                    lcs[i][j] = t;
                }
                else {
                    lcs[i][j] = l;
                    path[i][j] = 2;
                }
            } 
        }
    }
       int i = N-1; int j = M-1;
         bool done = false;
         string ans;
       while(!done){
           if(i<0 || j<0) done =true;
           else{
               //both are greater or equal to 0
               if(path[i][j] == 1){
                   //include it
                   ans.push_back(s[i]); i--; j--;
               }
               else if(path[i][j] == 2){
                    //go left
                    j--;
               }
               else if(path[i][j] == 3){
                   //go top
                 i--;
               }
           }
       }
       reverse(ans.begin(), ans.end());
       cout<<ans<<endl;
}

Measured memory_bytes: 70656