#include<bits/stdc++.h>
// iteration and input/output stream
#define rep(i,a,b) for(int i = int(a);i<=int(b);i++)
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define printarr(x) rep(i,0,x.size()-1) cout<<x[i]<<" "; cout<<endl;
#define all(v) v.begin(),v.end()
 
#define si(x) int x; scanf("%d", &x)
#define sll(x) ll x; scanf("%lld", &x)
#define pi(x) printf("%d", x)
#define pll(x) printf("%lld", x)
#define nl printf("\n")
#define tr(cont,it) \
for(decltype(cont.begin()) it = cont.begin(); it!= cont.end() ; it++)
 
#define endl "\n"
#define tc() int t; cin >> t ; while (t--)
//STL shortcuts
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define F first
#define S second
#define MP make_pair
 
// Error detection
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
 
using namespace std;
 
typedef long long int ll; // 64 bit integer
typedef unsigned long long int  ull; // 64 bit unsigned integer
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
 
inline void smax(int &x , int y) { x = max(x , y) ; }
inline void smin(int &x , int y) { x = min(x , y) ; }
 
#define MOD 1000000007
#define inf 4000000000000000000LL
#define SYNC std::ios::sync_with_stdio(false);  cin.tie(NULL);

string s,t;

// vector<vector<string>> dp;
vvi dp;
// 2 0
// 1 
vvi bp;//0 is left,1 is up, 2 is diagonal


int f(int i,int j)
{
    // trace2(i,j);
    // string cur = "";

    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    else if(i==0||j==0)
    {
        return dp[i][j] = 0;
    }    
    else
    {
        if(s[i-1]==t[j-1])
        {
            bp[i][j] = 2;//go diagonal
            return dp[i][j] = 1+f(i-1,j-1);
        }
        else
        {
            int a1 = f(i-1,j);
            int a2 = f(i,j-1);
            if(a1>=a2)
            {
                bp[i][j] = 1;//go up, i-=1
                return dp[i][j] = a1;
            }
            else
            {
                bp[i][j] =0; // go left , j-=1
                return dp[i][j] = a2;
            }
        }
    }
}


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("err.txt","w",stderr);
    #endif
    SYNC
    
    cin>>s>>t;
    s = s;
    t = t;
    int n = s.size();
    int m = t.size();
    dp.assign(n+1,vi(m+1,-1));//n*m
    bp.assign(n+1,vi(m+1,-1));

    // for (int i = 0; i < dp.size(); i++)
    // {
    //     for (int j = 0; j < dp[0].size(); j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    //dp[i][j] = lcs between s[0..i] and t[0..j]
    int lcs_l = f(n,m); //start from length
    string ans = "";
    int i =n,j = m;
    // trace1("agn\n");    
    // while(i>0 && j>0)
    // {
    //     trace1(ans);
    //     trace2(i,j);
    //     if(dp[i][j]==dp[i-1][j])
    //     {
    //         i-=1;
    //     }
    //     else if(dp[i][j]==dp[i][j-1])
    //     {
    //         j-=1;
    //     }
    //     else
    //     {
    //         i-=1;
    //         j-=1;
    //         ans = s[i] + ans;//append to front
    //     }
    // }
    string ans2 = "";
    // int dir = bp[n][m];
    i =n,j = m;
    // trace1("agn2\n");
    while (i>0 && j>0)
    {
        int dir = bp[i][j];
        trace1(ans2);
        trace2(i,j);
        trace1(dir);
        if(dir==0)
        {
            j-=1;
        }
        else if(dir==1)
        {
            i-=1;
        }
        else if(dir==2)
        {
            i-=1;
            j-=1;
            ans2 = s[i] +ans2;
        }
    }
    
    // cout<<ans<<"\n";
    cout<<ans2<<"\n";
    return 0;
}

Measured memory_bytes: 75928