Submission #29835850

---

Source Code Expand

s = input()
t = input()
dp = [[0] * (len(t) + 1) for i in range(len(s) + 1)]
prev = [[(-10, -10)] * (len(t) + 1) for i in range(len(s) + 1)]
dp[0][0] = 0
for i in range(len(s)):
    for j in range(len(t)):
        if dp[i + 1][j + 1] < dp[i + 1][j]:
            dp[i + 1][j + 1] = dp[i + 1][j]
            prev[i + 1][j + 1] = (i + 1, j)
        if dp[i + 1][j + 1] < dp[i][j + 1]:
            dp[i + 1][j + 1] = dp[i][j + 1]
            prev[i + 1][j + 1] = (i, j + 1)
        if s[i] == t[j] and dp[i + 1][j + 1] < dp[i][j] + 1:
            dp[i + 1][j + 1] = dp[i][j] + 1
            prev[i + 1][j + 1] = (i, j)
answer = ""
i, j = len(s), len(t)
while (i, j) != (-10, -10):
    if prev[i][j] == (i - 1, j - 1):
        answer = s[i - 1] + answer
    i, j = prev[i][j]
print(answer)

Submission Info

Judge Result