[BOJ][🟡5][백준#05582] 공통 부분 문자열

문제 출처

BAEKJOON Online Judge #5582

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 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 이하이다.

출력

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

예제

예제 1

입력

ABRACADABRA
ECADADABRBCRDARA

출력

5

예제 2

입력

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

출력

0

My Sol

def LCS(i, j):
    global memo, maxl
    if not i*j: return
    elif A[i]==B[j]:
        memo[i][j] = memo[i-1][j-1]+1
        maxl = max(maxl, memo[i][j])


A = '.'+input()
B = '.'+input()
I, J = len(A), len(B)
maxl = 0

memo = [[0]*J for _ in range(I)]
for i in range(I):
    for j in range(J):
        LCS(i, j)

print(maxl)

처음으로 DP를 이용해 풀어본 LCS 문제였다. 모든 자리의 알파벳에 대하여 일치하지 않는다면 0, 일치한다면 각각의 이전 알파벳까지의 연속 길이 + 1의 값을 memo에 부여한다. 이 문제는 최대 길이를 구하는 문제이므로, 일치할 때마다 전역의 maxl과 비교하여 갱신해주었다.

결과

맞았습니다!!