LCS

/*
   __Allahu Akbar__
   __All_praises_to_Allah__
   __Bismillahir_Rahmanir_Rahim__

   Author: Abdullah Al Nayem
   Studying B.Sc in CSE at Leading University.

   Practice, like you've never won. Perform, like you've never lost.
   Practice hard, play hard. Be hard to beat.

*/

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <bitset>
using namespace std;

#define MAX               32000
#define ll                long long
#define pb                push_back
#define mkp               make_pair
#define F                 first
#define S                 second
#define Sort_arr(arr,x)   sort(arr,arr+x)
#define Sortr_arr(arr,x)  sort(arr, arr+n,greater<int>())
#define SortS(str)        sort(str.begin(), str.end())
#define SortRS(str)       sort(str.rbegin(), str.rend())
#define arr_rev(n)        sort(n.begin(), n.end(), greater<int>())
#define gin(a)            getline(cin,a)
#define Sz(a)             a.size()
#define Ignore            cin.ignore()
#define sq(n)             (n*n)
#define cube(n)           (n*n*n)
#define min3(a, b, c)     min(a, min(b, c))
#define max3(a, b, c)     max(a, max(b, c))
#define YES               cout << "YES" << endl
#define NO                cout << "NO" << endl
#define pYES              printf("YES\n")
#define pNO               printf("NO\n")
#define bs                binary_search
#define lb                lower_bound
#define ub                upper_bound
#define all(a)            a.begin(),a.end()
#define Fast_read         ios_base::sync_with_stdio(false);

//#define SIZE_N 32000
//bitset <SIZE_N> bs;
//ll int primes[SIZE_N+5];
//vector<int> primes;

/*-----------------------Useful functions-----------------------*/

//ll int seive(){ll int i,j,total=0,val;for(i=2;i<=SIZE_N;i++) bs[i]=1;val=sqrt(SIZE_N)+1;for(i=2;i<val;i++)if(bs[i])for(j=i;j*i<=SIZE_N;j++)bs[i*j]=0;for(i=2;i<=SIZE_N;i++)if(bs[i])primes[total++]=i;return total;}
//void Sseive() {bool isPrime[MAX];for (int i = 0; i < MAX; ++i) isPrime[i] = true;for (int i = 3; i * i <= MAX; i += 2) {if (isPrime[i]) {for (int j = i * i; j <= MAX; j += i) {isPrime[j] = false;}}}primes.push_back(2);for (int i = 3; i < MAX; i += 2) {if (isPrime[i]) primes.push_back(i);}}void segSieve (ll l, ll r) {bool isPrime[r-l+1];for (int i = 0; i < r - l + 1; ++i) isPrime[i] = true;if (l == 1) isPrime[0] = false;for (int i = 0; primes[i]*primes[i] <= r; ++i) {int currentPrime = primes[i];ll base = (l/currentPrime)*currentPrime;if (base < l) base += currentPrime;for (ll j = base; j <= r; j += currentPrime) {isPrime[j-l] = false;}if (base == currentPrime) isPrime[base-l] = true;}for (int i = 0; i < r - l + 1; ++i) {if (isPrime[i]) cout << (i+l) << endl;}puts("");}
//ll int divisor_mcs(ll int N){ll int count=0,i;for (i=1;i<=sqrt(N);i++){if (N%i==0){count++;if (N/i!=i) count++;}}return count;}
//int divisor(int N){int i,val,count,sum;val=sqrt(N)+1;sum=1;for(i=0;primes[i]<val;i++){if(N%primes[i]==0){count=0;while(N%primes[i]==0){N/=primes[i];count++;}sum*=(count+1);}}if(N>1)sum=sum*2;return sum;}
//vector <int> primefactor(int n){int i;vector<int> primefact;for (i=2;i<=sqrt(n);i++){if (n%i==0){int count=0;while(n%i==0){n=n/i;count++;}while(count>0){primefact.pb(i);count--;}}}if (n!=1) primefact.pb(n);return primefact;}
//vector <int> all_divisor(int n){int i;vector<int> all_div;for (i=2;i<=sqrt(n);i++){if (n%i==0) all_div.pb(i);if (n/i!=i && n%i==0) all_div.pb(n/i);}sort(all_div.begin(),all_div.end());return all_div;}
//ll int GCD (ll int x, ll int y){if (x%y==0) return y; else return (GCD(y,x%y));}
//ll int LCM (ll int a,ll int b) {return (a/GCD(a,b))*b;}
//bool is_prime(ll int n){for (ll int i=2;i<=sqrt(n);i++){if (n%i==0) return false;}return true;}

/*------------------------------------------------------------------*/



string LCS( string str1, string str2)
{
    int m=str1.size();
    int n=str2.size();
    int L[m+1][n+1];

    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
        if (i == 0 || j == 0)
            L[i][j] = 0;
        else if (str1[i-1] == str2[j-1])
            L[i][j] = L[i-1][j-1] + 1;
        else
            L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
    int index = L[m][n];

    string res="";
    int i = m, j = n;
    while (i > 0 && j > 0)
    {
        if (str1[i-1] == str2[j-1])
        {
            res+=str1[i-1];
            i--; j--; index--;
        }

        else if (L[i-1][j] > L[i][j-1])
            i--;
        else
            j--;
    }
    reverse(res.begin(),res.end());
    return res;
}

int main()
{
    string str1,str2;
    cin>>str1>>str2;
    cout<<LCS(str1,str2)<<endl;

    return 0;
}