Consider the following variant of the longest common subsequence (LCS) problem:

You are given strings \(s\) and \(t\). Find the length of the LCS of \(s\) and \(t\).

To solve this problem, we define \(f(i, j)\) as the length of the LCS of the first \(i\) characters of \(s\) and the first \(j\) characters of \(t\). Let \(s_i\) denote the \(i\)-th character of \(s\) and \(t_j\) denote the \(j\)-th character of \(t\). By comparing whether \(s_i=t_j\), we obtain

\[ f(i, j)= \begin{cases} 0&\quad\text{if } i=0\text{ or }j=0,\\ f(i-1, j-1)+1&\quad\text{if } s_i=t_j,\\ \max(f(i-1,j),f(i,j-1))&\quad\text{otherwise.} \end{cases} \]

Thus, we can use a nested loop to compute \(f(|s|, |t|)\), the length of the LCS of \(s\) and \(t\), in \(O(|s|\cdot|t|)\) time.

To solve the original problem, we can iteratively backtrack through the DP array to find the subsequence that gives the longest length. Starting with \((i, j)=(|s|, |t|)\) and repeating as long as \(i\gt0\) and \(j\gt0\):

• If \(f(i, j)=f(i-1, j)\), we can drop the \(i\)-th character from \(s\) and still obtain the same LCS, so we update \(i\leftarrow i-1\).
• Otherwise, if \(f(i, j)=f(i, j-1)\), we can likewise drop the \(j\)-th character from \(t\) and update \(j\leftarrow j-1\).
• Otherwise, \(f(i,j)\) is equal to \(f(i-1,j-1)+1\), meaning the character \(s_i\) must contribute to the LCS. We record this \(s_i\) and update \(i\leftarrow i-1\) and \(j\leftarrow j-1\).

The recorded LCS will be reversed because the direction of our recovery is opposite to the direction we calculated \(f(i,j)\). Reversing this string gives a correct LCS of \(s\) and \(t\).

S = input()
T = input()
N = len(S)
M = len(T)

dp = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

result = []
i = N
j = M
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        result.append(S[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(result)))