#include <iostream>
#include <limits>
#include <cstdint>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <deque>
#include <stack>
#include <queue>
#include <utility> 
using namespace std;
typedef long long int l1;
typedef long long unsigned int lu1;
typedef long double ld;
#define FIO std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PI acos(-1.0)
#define pb push_back
// #define SORT(A) sort(A.begin(), A.end());
// #define REVERSE(A) reverse(A.begin(), A.end());
#define deb(x) cout << #x << " " << x << endl
#define PrintArray(arr) for(int i=0;i<(int)arr.size();i++)cout<<arr[i]<<" ";cout<<endl;
#define pii pair<int,int>
#define pll pair<long long int , long long int>
#define puu pair<long long unsigned , long long unsigned>
const int MOD = 1e9+7;

int dp[3*1000+10][3*1000+10];
int foo(string str1,int n, string str2,int m)
{
    // if(n==0 || m==0)
    // {
    //     return 0;
    // }
    // if(dp[n][m]!=-1)
    // {
    //     return dp[n][m];
    // }
    // if(str1[n-1]==str2[m-1])
    // {
    //     return dp[n][m] = 1+foo(str1,n-1,str2,m-1);
    // }
    // else
    // {
    //     return dp[n][m] = max(foo(str1,n,str2,m-1), foo(str1,n-1,str2,m));
    // }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0 || j==0) dp[i][j] = 0;
            else if(str1[i-1]==str2[j-1])
            {
                dp[i][j] = 1+dp[i-1][j-1];
            }
            else
            {
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
            }
            
        }
    }
}

int main()
{
    FIO;
    int t;
    t = 1;
    // cin>>t; 
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    for(int tc=0;tc<t;tc++)
    {   
        // int n,m;
        // cin>>n>>m;
        string str1,str2;
        cin>>str1;
        cin>>str2;
        int n = str1.size();
        int m = str2.size();
        memset(dp,-1,sizeof(dp));
        int cnt = foo(str1,n,str2,m);
        // cout<<foo(str1,n,str2,m)<<"\n";
        // for(int i=0;i<=n;i++)
        // {
        //     for(int j=0;j<=m;j++) cout<<dp[i][j]<<" ";
        //     cout<<"\n";
        // }
        string ans;
        int i = n, j = m;
        while(i>=1 && j>=1 )
        {
            // cout<<"i:"<<i<<"\n";
            // cout<<"j:"<<j<<"\n";
            if(dp[i][j]!=-1 && str1[i-1]==str2[j-1])
            {
                ans+=str1[i-1];
                i-=1;
                j-=1;
            }
            else if(dp[i][j]!=-1 && str1[i-1]!=str2[j-1])
            {
                if(dp[i][j-1]==-1 && dp[i-1][j]!=-1)
                {
                    i-=1;
                }
                else if(dp[i][j-1]!=-1 && dp[i-1][j]==-1)
                {
                    j-=1;
                }
                else if(dp[i][j-1]!=-1 && dp[i-1][j]!=-1)
                {
                    if(dp[i][j-1]>dp[i-1][j])
                    {
                        j-=1;
                    }
                    else
                    {
                        i-=1;
                    }
                    
                }
                else break;
            }
            else if(dp[i][j]==-1) break;
            else break;   
        }
        reverse(ans.begin(),ans.end());
        cout<<ans<<"\n";
    }
    return 0;
}

Measured memory_bytes: 35840