[アルゴリズム/規格]9251号:LCS(python)

a1 = input()
a2 = input()
len1 = len(a1)
len2 = len(a2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for i in range(1, len1 + 1):
    for j in range(1, len2 + 1):
        if a1[i - 1] == a2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[len1][len2])