DP를 이용한 최장 공통 부분 문자열(LCS) 알고리즘

LCS 알고리즘은 흔히 알려진 DP 를 이용한 매칭 알고리즘이다.

두 수열 혹은 문자열 사이에 공통으로 존재하는 부분 문자열을 찾는 알고리즘으로 가령, 다음과 같은 예시를 봐보자.

SETAPPLE 

EATMANY

위의 예시에서 공통으로 존재하는 부분 문자열은 E-T-A 이다. 순서가 보장되면서 양쪽에 모두 존재하는 똑같은 패턴의 공통 문자열이다.

문제를 해결하기 위해서 가장 쉬운 방법은 두 문자열에 대한 Nested Loop 를 돌면서 완전탐색으로 순서를 기록하면 되지만, 이렇게 하면 매우 복잡하면서도

비효율적인 알고리즘이 된다.

그래서 흔히 알려진 알고리즘은 다음과 같은 DP 의 Memoization 테크닉을 사용한 알고리즘이다.

    public int findLCS(String a, String b) {

        int[][] dp = new int[a.length()+1][b.length()+1];

        int result = Integer.MIN_VALUE;

        for(int i=1; i<=a.length(); i++) {

            for(int j=1; j<=b.length(); j++) {

                if(a.charAt(i-1) == b.charAt(j-1)) {

                    dp[i][j] = dp[i-1][j-1] + 1;

                } else {

                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

                }

                result = Math.max(result, dp[i][j]);

            }

        }

        return result;

    }

위의 코드를 해석해보자.

DP에 친숙하다면 위의 코드는 그다지 어렵지 않다. 2차원배열 dp 는 두 문자열에 대한 배열을 저장한다.

즉, 다음과 같이 정의된다.

dp[i][j] => 문자열1의 i 인덱스 까지에 대한 부분문자열과 문자열2의 j 인덱스 까지에 대한 부분문자열 간의 최장 공통 부분 수열 길이를 저장.

이렇게 하면, 다음과 같은 관계가 도출된다.

문자열1의 i번째 문자와 문자열2의 j번째 문자가 같다면, 해당 위치에서의 LCS 길이는 그 전길이까지의 최장 공통 부분 수열의 길이보다 1만큼 증가한 값이 된다.

dp[i][j] = dp[i-1][j-1] + 1

반면 같지 않다면, 다음과 같이 문자열1의 i-1 번째까지의 부분 문자열과 문자열2의 j-1 번째의 부분 문자열 간의 최장 부분 길이 중 더 긴쪽이 기록 된다.

dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

이와 같은 식을 이용해 만든 dp 배열을 표로 기록해보자.

이제 dp 배열은 부분 문자열의 길이에 대한 모든 정보를 포함하고 있다.

E A T M A N Y

S 0 0 0 0 0 0 0

E 1 1 1 1 1 1 1

T 1 1 2 2 2 2 2

A 1 2 2 2 3 3 3

P 1 2 2 2 3 3 3

P 1 2 2 2 3 3 3

L 1 2 2 2 3 3 3

E 1 2 2 2 3 3 3

오른쪽 아래에서부터 왼쪽 위까지 (두 문자열의 끝부분에서부터 시작부분까지) 반복하면서 숫자가 처음으로 작아지는 시점(역으로 생각하면 처음으로 부분 문자열 길이기 증가하는 시점이다.) 을 찾으면,

어떤 문자열이 공통 부분 문자열인지도 알 수 있다. 다음 굵게 표시된 요소들이 부분 문자열이 된다.

물론 표의 최댓값을 찾는다면 LCS 의 길이 또한 쉽게 구할 수 있다.