[백준][Python] 9251 LCS

오랜만에 푸는 LCS(substring), string과 편집거리도 같이 연습했습니다.

 

import sys
input = sys.stdin.readline

a, b = input().strip(), input().strip()
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)] 

for i in range(n): 
    for j in range(m): 
        dp[i + 1][j + 1] = dp[i][j] + 1 if a[i] == b[j] else max(dp[i + 1][j], dp[i][j + 1]) 

print(dp[-1][-1])