최장 공통 부분 수열 (LCS, Longest Common Subsequence) 알고리즘

LCS 알고리즘

• LCS는 주로 최장 공통 부분 수열(Longest Common Subsequence)을 말한다.
• LCS는 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.

최장 공통 부분 수열과 최장 공통 문자열의 구분

최장 공통 부분 수열(Longest Common Subsequence)

점화식

두 문자가 다를 경우
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

두 문자가 같을 경우
LCS[i][j] = LCS[i-1][j-1] + 1

 

동작 과정

1. 문자열 A, 문자열 B를 한 글자씩 비교한다.

2. 두 문자가 다르다면 LCS[i-1][j] 와 LCS[i][j-1] 중 큰 값을 표시

3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 1을 더해준다.

4. 위 과정을 반복한다.

 

구현 과정

[Step 1] 앞마진이 0인 2차원 배열을 생성, ABCDEF, GBCDFE 문자열을 한 글자씩 비교

[Step 2] G를 ABCDEF와 한 글자씩 비교, 문자가 같지 않다면 LCS[i][j] 값은 max(LSC[i-1][j], LSC[i][j-1])

[Step 3] 다음으로 B를 ABCDEF와 한 글자씩 비교, 같은 문자가 존재하면 LCS[i][j] 값은 LSC[i-1][j-1] + 1

[Step 4] 다음으로 C를 ABCDEF와 한 글자씩 비교, 같은 문자가 존재하면 LCS[i][j] 값은 LSC[i-1][j-1] + 1,

                 문자가 같지 않다면 LCS[i][j] 값은 max(LSC[i-1][j], LSC[i][j-1])

[Step 5] 다음으로 D를 ABCDEF와 한 글자씩 비교, 같은 문자가 존재하면 LCS[i][j] 값은 LSC[i-1][j-1] + 1,

                 문자가 같지 않다면 LCS[i][j] 값은 max(LSC[i-1][j], LSC[i][j-1])

[Step 6] 다음으로 F를 ABCDEF와 한 글자씩 비교, 같은 문자가 존재하면 LCS[i][j] 값은 LSC[i-1][j-1] + 1,

                 문자가 같지 않다면 LCS[i][j] 값은 max(LSC[i-1][j], LSC[i][j-1])

[Step 7] 다음으로 E를 ABCDEF와 한 글자씩 비교, 같은 문자가 존재하면 LCS[i][j] 값은 LSC[i-1][j-1] + 1,

                 문자가 같지 않다면 LCS[i][j] 값은 max(LSC[i-1][j], LSC[i][j-1])

[Step 8] 최댓값을 찾으면 Longest Common Subsequence 탐색 종료

Code

import sys
sys.stdin = open('input.txt', 'r')
input = sys.stdin.readline

string1, string2 = input().rstrip(), input().rstrip()
l1, l2 = len(string1)+1, len(string2)+1
# LCS dp 생성
LCS = [[0] * l1 for _ in range(l2)]

for i in range(1, l2) :
    for j in range(1, l1) :
        # 문자가 같을 경우
        if string2[i-1] == string1[j-1] :
            LCS[i][j] = LCS[i-1][j-1] + 1
        # 문자가 같지 않을 경우
        else :
            LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])

print(LCS[-1][-1])