Common_Subsequence

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
#define vpll vector<pair<ll, ll>>
#define vpi vector<pair<int, int>>
#define p_b pop_back
#define fl(i, a, b) for(int i = a; i <= b; i++)
#define tests() int t; cin >> t; while(t--)
#define MOD (ull)1000000007
using namespace std;

template <typename T>
void input(vector<T>& v, int n){
    for(int i = 0; i < n; i++){
        T x; cin >> x; v.pb(x);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin >> s >> t;
    string dp[s.length()+1][t.length()+1] = {""};
    for(int i = 0; i <= s.length(); i++){
        for(int j = 0; j <= t.length(); j++){
            dp[i][j] = "";
        }
    }
    for(int i = 0; i <= s.length(); i++){
        for(int j = 0; j <= t.length(); j++){
            if(i == 0 || j == 0){
                dp[i][j] = "";
            } else{
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1]+s[i-1];
                } else{
                    if(dp[i-1][j].length() > 0 || dp[i][j-1].length() > 0){
                        if(dp[i-1][j].length() >= dp[i][j-1].length()){
                            dp[i][j] = dp[i-1][j];
                        } else{
                            dp[i][j] = dp[i][j-1];
                        }
                    } else{
                        dp[i][j] = "";
                    }
                }
            }
        }
    }
    cout << dp[s.length()][t.length()] << "\n";
    return 0;
}