[LCS] Longest Common Subsequence (최장 공통 부분 문자열)

LCS 알고리즘이란..?

한국말로 번역해보면 "최장 공통 부분 문자열"이다.

 

여기서 Subsequence와 Substring의 차이에 대해 이해해야만 한다.

둘의 차이는 연속성이다.

 

연속된 부분 문자열을 만족하는 것은 Substring이고

 

연속되지 않은 부분 문자열이라면 Subsequence이다.

 

"ACAYKP"

"CAPCAK"

 

가장 긴 Substring은 CA이고

가장 긴 Subsequence는 ACAK이다.

 

LCS 를 구하는 방법 (다이나믹 프로그래밍)

1. 먼저 dp배열을 만들어준다. 0열 0행을 추가적으로 만들어준다. (편의를 위해)
2. 배열1과 배열2를 비교하는데 배열2의 문자하나를 잡아서 배열1의 모든 문자와 비교해나간다.
   
   1. 문자를 비교해서 값이 같으면 왼쪽 위(현재 문자를 포함하지 않은 최댓값)에 +1를 해준다.
   2. 값이 다르다면 위나 왼쪽(현재 값을 검사하고 나온 최댓값)에서 큰값을 대입해준다.
3. 2과정이 끝나면 배열2의 해당문자까지 최장 공통 부분 문자열을 구한 것이다.
4. 이전에 구했던 최장 부분 수열을 이용해서 끝까지 배열을 완성해나가면 된다.

배열을 완성한 후 배열에서 가장 큰 값이 "최장 공통 부분 문자열"이라고 볼 수 있다.

 

LCS 백준 문제 (9251번)

www.acmicpc.net/problem/9251

9251번: LCS

#코드

arr1 = [0] + list(input())
arr2 = [0] + list(input())

dp = [[0] * len(arr1) for _ in range(len(arr2))]

for i in range(1, len(arr2)):
    char = arr2[i]
    for j in range(1, len(arr1)):
        if arr2[i] == arr1[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
mx = 0
for row in dp:
    mx = max(mx, max(row))
print(mx)