[ BOJ ] 5582 : 공통 부분 문자열 ( GOLD 5 ) / Python

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

풀이 과정

최장 연속 공통 부분 문자열을 찾는 문제이다.

dp[i][j] = a[i-1], b[j-1] 까지의 연속 공통 부분 문자열 길이 이므로, 이전에 같은 문자열이 있었다면 연속으로 길이를 누적할 수 있도록 DP 테이블을 구성했다.

이후 완전 탐색으로 최대 길이를 찾으면 된다.

import sys
input = sys.stdin.readline

a = input().rstrip()
b = input().rstrip()

dp = [[0 for _ in range(len(b)+1)] for _ in range(len(a)+1)]

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

max_value = 0
for d in dp: 
    max_value = max(max_value, max(d))
print(max_value)