s = eval(input())

t = eval(input())



dp = [[0]*(len(t)+1) for i in range(len(s)+1)]



for i in range(len(s)):

    for j in range(len(t)):

        if s[i] == t[j]:

            dp[i+1][j+1] = max(dp[i][j] + 1, dp[i+1][j], dp[i][j+1])

        else:

            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])



ans = []

i = len(s) - 1

j = len(t) - 1

while True:

    if i < 0 or j < 0:

        break

    if dp[i+1][j+1] == dp[i+1][j]:

        j -= 1

    elif dp[i+1][j+1] == dp[i][j+1]:

        i -= 1

    elif dp[i+1][j+1] == dp[i][j] + 1:

        ans.append(t[j])

        i -= 1

        j -= 1



print(("".join(ans)[::-1]))
def lcs(str1, str2):

    """文字列str1, str2の最長共通部分列(Longest Common Subsequence, LCS)を求める。

    計算量 O(|str1||str2|)

    """

    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

    for i in range(len(str1)):

        for j in range(len(str2)):

            if str1[i] == str2[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])



    # 復元

    res = ''

    i, j = len(str1), len(str2)

    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:

            res = str1[i - 1] + res

            i -= 1

            j -= 1



    return res





s = eval(input())

t = eval(input())

print((lcs(s, t)))
s = eval(input())
t = eval(input())
dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
ans = []
i = len(s) - 1
j = len(t) - 1
while True:
    if i < 0 or j < 0:
        break
    if dp[i + 1][j + 1] == dp[i + 1][j]:
        j -= 1
    elif dp[i + 1][j + 1] == dp[i][j + 1]:
        i -= 1
    elif dp[i + 1][j + 1] == dp[i][j] + 1:
        ans.append(t[j])
        i -= 1
        j -= 1
print(("".join(ans)[::-1]))

def lcs(str1, str2):
    """文字列str1, str2の最長共通部分列(Longest Common Subsequence, LCS)を求める。
    計算量 O(|str1||str2|)
    """
    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[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])
    # 復元
    res = ""
    i, j = len(str1), len(str2)
    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:
            res = str1[i - 1] + res
            i -= 1
            j -= 1
    return res


s = eval(input())
t = eval(input())
print((lcs(s, t)))

+def lcs(str1, str2): +    """文字列str1, str2の最長共通部分列(Longest Common Subsequence, LCS)を求める。 +    計算量 O(|str1||str2|) +    """ +    dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)] +    for i in range(len(str1)): +        for j in range(len(str2)): +            if str1[i] == str2[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]) +    # 復元 +    res = "" +    i, j = len(str1), len(str2) +    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: +            res = str1[i - 1] + res +            i -= 1 +            j -= 1 +    return res + + -dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)] -for i in range(len(s)): -    for j in range(len(t)): -        if s[i] == t[j]: -            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1]) -        else: -            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]) -ans = [] -i = len(s) - 1 -j = len(t) - 1 -while True: -    if i < 0 or j < 0: -        break -    if dp[i + 1][j + 1] == dp[i + 1][j]: -        j -= 1 -    elif dp[i + 1][j + 1] == dp[i][j + 1]: -        i -= 1 -    elif dp[i + 1][j + 1] == dp[i][j] + 1: -        ans.append(t[j]) -        i -= 1 -        j -= 1 -print(("".join(ans)[::-1])) +print((lcs(s, t)))