#include "bits/stdc++.h"
#include<stdio.h>
#include <sstream>
#define pi 3.141592653589793238462
#define limit 100005
#define mo 1000000007;
typedef long long int lli;
typedef unsigned long long int ulli;
const lli mod=9999999999999983;
lli primes[6]={1125899906842597,1495921043,1005985879,1495921043,1005985879,1495921043};
using namespace std;
vector<lli>adj[2000009];
lli parent[2000009];
lli vis[2000009];
lli level[2000009];
lli dist[2000009];
lli dp[5009][5009][3];
lli arr[2000009];
lli brr[2000009];
lli crr[2000009];
lli hashing[2000009];
lli ar[509][509];
lli br[509][509];
lli cr[509][509];
string str1,str2;
lli cnt,flag;
vector<char>vect;
map<lli,lli>mp1,mp2;



void path(lli n1,lli n2)
{

    //cout<<"n1="<<n1<<" "<<"n2="<<n2<<endl;

    if(n1<0||n2<0)
        return ;

    if(str1[n1]==str2[n2]&&mp1[n1]==0&&mp2[n2]==0)
    {
        vect.push_back(str1[n1]);
        mp1[n1]=1;
        mp2[n2]=1;
    }

        /*

    if(flag==1)
    {
        return;
    }

    cnt--;

    if(cnt<0)
    {
        flag=1;
        return;
    }


    cout<<"rem="<<cnt<<endl;

    */


    if(dp[n1][n2][2]==1)
    {
        //if(str1[n1-1]==str2[n2]&&n1-1>=0&&n2>=0)
             //cout<<str1[n1-1]<<endl;
             //vect.push_back(str1[n1-1]);
        path(n1-1,n2);
    }
    else if(dp[n1][n2][2]==2)
    {
       //if(str1[n1]==str2[n2-1]&&n2-1>=0&&n1>=0)
             //cout<<str1[n1]<<endl;
            // vect.push_back(str1[n1]);
        path(n1,n2-1);
    }
    else
    {
        //if(str1[n1-1]==str2[n2-1]&&n1-1>=0&&n2-1>=0)
             //cout<<str1[n1-1]<<endl;
             //vect.push_back(str1[n1-1]);
        path(n1-1,n2-1);
    }
}





lli solve(lli n1,lli n2)
{
    lli ans,ans1,ans2,ans3,res;

    if(dp[n1][n2][1]!=-1)
        return dp[n1][n2][1];

        if(n1<0||n2<0)
            return 0;

     if(str1[n1]==str2[n2])
        ans=1;
     else
        ans=0;

    // return dp[n1][n2]=max(max(,),));

     ans1=solve(n1-1,n2);
     ans2=solve(n1,n2-1);
     ans3=ans+solve(n1-1,n2-1);

     res=max(max(ans1,ans2),ans3);

     //cout<<"ans1="<<ans1<<" "<<"ans2="<<ans<<" "<<"an3="<<ans3<<endl;

     if(ans1==res)
     {
         dp[n1][n2][2]=1;
     }
     else if(ans2==res)
     {
         dp[n1][n2][2]=2;
     }
     else if(ans3==res)
     {
         dp[n1][n2][2]=3;
     }

     //cout<<"n1="<<n1<<" "<<"n2="<<n2<<" "<<"dp="<<res<<endl;

     return dp[n1][n2][1]=res;;
}


int main()
{
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    int start_s = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    //vector<lli>vect,vt,vct;
    //vector<lli>::iterator itt;
    set<lli>st;
    set<lli>::iterator itr;
    //map<lli,lli>mp;
    //map<lli,lli>::iterator it;


    lli i,j,k,n,m,q,t,a,b,c,maxi=INT_MIN,mini=INT_MAX,sum=0,ans=0,res=0,val=0,ans1=0,ans2=0,rem=0,diff=0,l,r,e,index,val1=0,val2=0,x,y,z,h=0,u,v,mid,len,tot,fl=0;

    cin>>str1;
    cin>>str2;
    
    
    memset(dp,-1,sizeof(dp));

    cnt=solve(str1.size()-1,str2.size()-1);

    if(cnt==0)
        return 0;

    //cout<<"cnt="<<cnt<<endl;

    path(str1.size()-1,str2.size()-1);

     for(i=vect.size()-1;i>=0;i--)
    //if(vect[i]!=' ')
        cout<<vect[i];
}


Measured memory_bytes: 638080