[알고리즘] 최장 공통 문자열(LCS : Longest Common Substring) 알고리즘

LCS(Longest Common Substring)란

최장 공통 부분 문자열은 두 문자열이 주어졌을 때, 두 문자열에 포함된 가장 긴 공통 부분 문자열을 찾는 문제입니다.

 

유사한 문제로 최장 공통 부분 수열(LCS: Longest Common Subsequence) 있고, 오늘은 최장 공통 부분 문자열에 대해서 알아보도록 하겠습니다.

 

 

예를 들어

ABCDE,
BCCAR

와 같은 두 개의 문자열이 주어졌다고 가정해봅시다.

 

 

ABCDE는 A, AB, ABC, .., B, BC, .., ABCDE등 다양한 부분 문자열로 나타낼 수 있습니다.

 

이 때, ABCDE 와 BCCARD 각각이 가지는 부분 문자열 중 동일하게 포함하는 가장 긴 부분 문자열을 찾는 문제입니다.

 

 

 

 

풀이

일반적인 최장 공통 부분 문자열은 2차원 DP를 통해서 풀 수 있습니다.

 

아래 풀이 개념은 두 문자열이 주어졌을 때 하나의 글자씩 비교하다가 같은 문자가 나오면 한칸씩 앞으로 이동하면서 같은 문자가 나온 길이를 계산하는 방법이라고 보시면 됩니다.

 

 

 

0) init

N = "0ABCDE"
M = "0BCCAR"

dp = [N.length][M.length]

먼저 ACAYKP를 N, CAPCAK M이라고 가정합니다.

두 배열의 길이만큼 2차원 배열을 생성합니다.

 

 

 

1) dp 완성

for (i = 1; i >= N.length) {
	for (j = 1; j >= M.length) {
    	if (N[i] != M[i]) {
        	dp[i][j] = 0;
        }
        if (N[i] == M[i]) {
        	dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    }
}

N(i)과 M(j)의 글자를 하나씩 비교하면서 두 문자가 다를 때 dp[i][j]에 0을 넣습니다.

만약 비교한 문자가 같다면 dp[i - 1][j - 1]의 값에 +1한 값을 dp[i][j]에 넣습니다.

 

 

 

그림으로 살펴보자면 초기 dp 테이블은 위와 같습니다.

 

 

이 때 dp 테이블의 역할은 지금까지 계산한 가장 긴 문자열 길이를 저장하는 것입니다.

 

 

 

처음 두 배열의 첫 번째 위치의 요소를 살펴보면 A와 B로 서로 다르므로 0을 dp 테이블에 삽입합니다.

 

 

 

다음 비교는 두 문자열이 같은 문자를 가지므로 앞의 문자들이 서로 같은지를 비교하여 저장해주시면 됩니다.

 

N의 앞에 문자는 A이고, M의 앞에 문자는 없기 때문에 0입니다.

 

 

위와 같이 문자열 비교 시 첫 문자의 앞에 대한 정보를 저장하기 위해서 dp의 길이를 N + 1, M + 1로 하고 맨 첫번째 줄은 0으로 초기화 해둔 것입니다. 

 

 

 

같은 방법으로 N의 C와 M의 C를 비교할 때는 서로 같은 문자이기 때문에, 각 문자열의 앞 문자가 같은지를 확인해야 합니다. 

 

 

우리는 원래라면 i-1번째 문자와 j-1번째 문자, i-2번째 문자와 j-2번째 문자, ... 와 같이 앞선 문자가 서로 같은지 계속 확인할 필요가 있었습니다.

 

 

하지만 dp 테이블에 앞의 문자를 비교한 정보를 이미 저장하고 있기 때문에, dp[i-1][j-1] + 1로 N의 i번째 문자와 M의 j번째 문자까지 동일한 문자열의 길이를 쉽게 파악할 수 있습니다.

 

 

 

3) 정답 도출

결국 마지막까지 모든 작업을 완료하면 위와 같은 dp 테이블이 완성 됩니다.

 

앞선 예제의 가장 긴 문자열은 BC이고 해당 길이는 2입니다. 

 

이를 dp 테이블에서 가장 큰 수를 찾는 것으로 쉽게 결과 확인이 가능합니다.

 

 

 

 

관련 문제

[백준] 5582 공통부분 문자열

문제

https://www.acmicpc.net/problem/5582

 

풀이

https://angelplayer.tistory.com/514