[백준][Python] 5582 공통 부분 문자열 : LCS

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

LCS에서 연속성만 부여하면 된다.

같을때 대각선 위값을 계승. 틀릴때 그냥 0

 

import sys
input = sys.stdin.readline

str1, str2 = (input().rstrip() for _ in range(2))
n, m = len(str1), len(str2)
dp = [[0]*(m+1) for _ in range(n+1)]
max_v = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] > max_v:
                max_v = dp[i][j]
print(max_v)