LCS

#include <bits/stdc++.h>

using namespace std;

#define ll long long

/*
// Recursive 
int LCS(string &s, string &t, int i, int j, vector<vector<int>>&dp) {
    if (i == 0 or j == 0)return 0;
    if (dp[i][j] != -1)return dp[i][j];

    if (s[i - 1] == t[j - 1]) {
        return dp[i][j] = max(1 + LCS(s, t, i - 1, j - 1, dp), max(LCS(s, t, i - 1, j, dp), LCS(s, t, i, j - 1, dp)));
    }

    return dp[i][j] = max(LCS(s, t, i - 1, j, dp), LCS(s, t, i, j - 1, dp));
}
*/

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    string s, t;
    cin >> s >> t;

    int n = s.size(), m = t.size();
    
    /*
    
    If Recursive Call this Use this
    vector<vector<int>>dp(n + 1, vector<int>(m + 1, -1));
    cout << LCS(s, t, n-1, m-1, dp);
    
    */

    vector<vector<int>>dp(n + 1, vector<int>(m + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = max(1 + dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    /*

    LCS printing...

    int i = n, j = m;

    string ss = "";

    while (i and j) {
        if (s[i - 1] == t[j - 1]) {
            ss += s[i - 1];
            i--; j--;
        }
        else {
            if (dp[i - 1][j] < dp[i][j - 1]) {
                j--;
            }
            else {
                i--;
            }
        }
    }


    reverse(ss.begin(), ss.end());

    cout << ss << '\n';

    */

    return 0;
}