#include <iostream>
#include <string>
#include <bits/stdc++.h>

using namespace std;

// too slow, there are at least two reasons
// 1. recursive call of function
// 2. copy of string s and t
string backtrack(const vector<vector<int>> f, string s, string t, int i, int j)
{
    if (i == 0 || j == 0)
        return "";
    if (s[i - 1] == t[j - 1])
    {
        return backtrack(f, s, t, i - 1, j - 1) + s[i - 1];
    }
    if (f[i][j - 1] > f[i - 1][j])
    {
        return backtrack(f, s, t, i, j - 1);
    }
    return backtrack(f, s, t, i - 1, j);
}

auto LCSMaybeFatser(const string &s, const string &t)
{
    int s_len = s.size();
    int t_len = t.size();

    vector<vector<int>> f;
    f.resize(s_len + 1, vector<int>(t_len + 1));
    for (size_t i = 1; i < s_len + 1; ++i)
    {
        for (size_t j = 1; j < t_len + 1; ++j)
        {
            if (s[i - 1] == t[j - 1])
            {
                f[i][j] = 1 + f[i - 1][j - 1];
            }
            else
            {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]);
            }
        }
    }

    // iterative method
    int i = s_len, j = t_len;
    int lcs_len = f[i][j];
    string lcs(lcs_len, '0');
    while (i > 0 && j > 0)
    {
        if (s[i - 1] == t[j - 1])
        {
            lcs[lcs_len - 1] = s[i - 1];
            --i;
            --j;
            --lcs_len;
        }
        else if (f[i][j - 1] >= f[i - 1][j])
        {
            --j;
        }
        else
        {
            --i;
        }
    }

    return lcs;
}

auto LCS(string s, string t)
{
    int s_len = s.size();
    int t_len = t.size();

    vector<vector<int>> f;
    vector<int> fst_row;
    for (size_t i = 0; i < t_len + 1; ++i)
    {
        fst_row.push_back(0);
    }
    f.push_back(fst_row);

    for (size_t i = 1; i < s_len + 1; ++i)
    {
        vector<int> cur_row{0};
        for (size_t j = 1; j < t_len + 1; ++j)
        {
            if (s[i - 1] == t[j - 1])
            {
                // lcs += s[i-1];
                cur_row.push_back(1 + f[i - 1][j - 1]);
            }
            else
            {
                cur_row.push_back(max(cur_row[j - 1], f[i - 1][j]));
            }
        }
        f.push_back(cur_row);
    }

    // for (auto &&row : f)
    // {
    //     for (auto &&e : row)
    //     {
    //         cout << e << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";

    // return f;
    // string lcs = backtrack(f, s,t, s_len, t_len);

    // iterative method
    int i = s_len, j = t_len;
    int lcs_len = f[i][j];
    string lcs(lcs_len, '0');
    while (i > 0 && j > 0)
    {
        if (s[i - 1] == t[j - 1])
        {
            lcs[lcs_len - 1] = s[i - 1];
            --i;
            --j;
            --lcs_len;
        }
        else if (f[i][j - 1] >= f[i - 1][j])
        {
            --j;
        }
        else
        {
            --i;
        }
    }

    return lcs;
}

// int AA_LCS(string s, string t)
// {
//     int s_len = s.size();
//     int t_len = t.size();

//     vector<vector<int>> f;
//     int fij = (s[0] == t[0] ? 1 : 0);
//     int f_i1_j = (s[1] == t[0] && s[1] != s[0] ? fij + 1 : fij);
//     int f_i_j1 = (t[1] == s[0] && t[1] != t[0] ? fij + 1 : fij);
//     int f_i1_j1 = (s[1] == t[1] ? f_ij + 1 : max(f_i1_j, f_i_j1));

//     for (size_t i = 1; i < s_len; ++i)
//     {
//         for (size_t j = 1; j < t_len; ++j)
//         {
//         }
//     }
// }

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    // cout << LCS(s, t) << "\n";
    cout << LCSMaybeFatser(s, t) << "\n";
}

Measured memory_bytes: 35584