[CLRS] [14-3] Dynamic Programming - Longest Common Subsequence(LCS)

1. Longest Common Subsequence(LCS)

- LCS에 대해서 알아가기 전에 substring과 subsequence의 차이에 대해서 알아보자.

- substring : 연속된 부분 문자열

- subsequence : 연속되지 않은 부분 문자열

 

- 여기서 LCS는 subsequence가 최대길이를 가질때를 알고 싶기에 나오게 된 개념이다.

2. LCS 구하기

- DP로 효율적으로 문제를 해결 가능하다.

- LCS는 2개의 문자열을 비교하여 최장인 subsequence를 구해야한다.

- 문자열 'BDCABA' 와 'ABCBDAB'가 있다고 생각해보자.

- 여기서 하나의 문자열을 기준 문자열, 다른 문자열을 비교 문자열로 가정한다.

- 위 표를 보면 문자열 맨 앞에 0을 추가해주었다.

- 첫번째 행에 A값을 집어넣어보자. 각 테이블에 들어가는 값들은 LCS가 들어간다.

- 여기서 [A,C]의 의미는 'A'와 'BDC'사이의 LCS길이를 의미한다.

 

- 끝까지 반복하면 다음과 같다.

 

- 테이블의 값을 구할 때 같은 문자가 나오면 이전까지의 LCS의 길이에 +1 을 해준다.

- 여기서 이전까지의 LCS의 길이는 왼쪽 위 대각선의 값을 의미한다.

- 그래프의 값을 구하는 규칙은 다음과 같다

'''

i) 행과 열의 문자가 같다면 [i,j] = [i-1,j-1] + 1

ii)행과 열의 문자가 다르다면 [i,j] = max([i-1,j],[i,j-1])

'''

 

- 여기서 LCS는 BCBA가 된다.

 

3. Code 

standard_string = input()
compare_string = input()

dp_matrix = [[0] * (len(standard_string)+1) for _ in range(len(compare_string)+1)]
result = ''
for i in range(1,len(compare_string)+1):
    for j in range(1,len(standard_string)+1):
        if compare_string[i-1] == standard_string[j-1]:
            dp_matrix[i][j] = dp_matrix[i-1][j-1] + 1
        else:
            dp_matrix[i][j] = max(dp_matrix[i-1][j],dp_matrix[i][j-1])
            
            
length = -1
i, j = len(compare_string) , len(standard_string)
while length != 0:
    if dp_matrix[i][j] == dp_matrix[i-1][j]:
        i -=1
        length = dp_matrix[i][j]
    elif dp_matrix[i][j] == dp_matrix[i][j-1]:
        j -= 1
        length = dp_matrix[i][j]
    else:
        result += compare_string[i-1]
        i -= 1
        j -= 1
        length = dp_matrix[i][j]
        

print(result[::-1])