LCS - 최장 공통 부분 수열

LCS?

• LCS (longest common substring)는 두 문자열 사이에 가장 긴 공통 부분 문자열을 구하는 문제이다.
• dp를 이용해 쉽게 해결할 수 있다!

 

 

str1 = "ABCGI"
str2 = "ACGIK"
dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
result = ""
for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        if str1[i - 1] == str2[j - 1]:
            result += str1[i - 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[-1][-1], result)
# 4, ACGI