문자열 알고리즘 (4) - 최장 공통부분 문자열 (Longest Common String)

1. 알고리즘 개요

최장 공통부분 문자열은 두 문자열에서 공통되는 공통문자열 중 가장 긴 문자열을 찾아내는 방법임.

 

이는 최장부분 공통부분 수열과 다른데, 최장 공통부분 문자열은 반드시 부분 문자열이 연결된 형태여야하고, 최장 공통부분 수열은 떨어져있어도 상관없음.

 

위처럼 최장 공통부분 수열은 중간에 문자가 떨어져 있어도 되고, 최장 공통부분 문자열은 중간에 문자가 떨어져있으면 안됨. 우리는 문자열 처리 알고리즘을 공부하고 있기 때문에 최장공통부분 문자열에 대해 알아볼 것임.

 

2. 소스코드

public class LongestCommonStrings {
    private static int MAX = 1 + 10;
    private static String string1 = "banaan";
    private static String string2 = "vbankn";
    private static int[][] cache = new int[MAX][MAX];

    public static void main(String[] args) {
        LongestCommonStrings lcs = new LongestCommonStrings();
        string1 = '\0' + string1;
        string2 = '\0' + string2;
        int result = 0;

        for (int i = 0; i < string1.length(); i++) {
            for (int j = 0; j < string2.length(); j++) {
                result = Math.max(result, lcs.lcs_memo(i, j));
            }
        }

        System.out.println(result);
    }

	// 재귀함수
    public int lcs(int i, int j) {
        if (i == 0 || j == 0)
            return 0;

        if (string1.charAt(i) == string2.charAt(j))
            return lcs(i - 1, j - 1) + 1;

        else
            return 0;
    }

	// 메모이제이션
    public int lcs_memo(int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (cache[i][j] != 0) return cache[i][j];

        if (string1.charAt(i) == string2.charAt(j))
            cache[i][j] = lcs(i - 1, j - 1) + 1;
        else
            cache[i][j] = 0;

        return cache[i][j];
    }

 

3. 분석

최장 공통부분 문자열은 위와 같이 유도됨. 만약 String1[i]와 String2[j]가 같았다면 LCS[i-1, j-1]의 값에 1을 더한 값을 새로운 LCS[i, j] 값으로 취한다. (대각선 왼쪽 위 방향의 수에 1을 더한 값을 취함)

 

이 때, 반드시 두 문자열의 가장 앞칸은 비워둬야함. 때문에 코드에서도 String1 앞에 null문자(\0), String2 앞에 null 문자(\0)를 추가했다. 왜냐하면 만약 두 문자열 중 어느것이라도 첫번째 문자가 일치했다면, LCS[i-1, ?] 혹은 LCS[?, j-1]을 계산해야하는데 i=0이거나 j=0이면 가장 앞칸이기 때문에 LCS[-1, ?]나 LCS[?, -1]이 되어 음수 인덱스로 참조하게 되고 에러를 발생시키게 된다. 때문에 행렬의 인덱스를 1부터 시작하게 만들어줘야 한다.

 

결론적으로 최장 공통부분 문자열 문제는 다음과 같은 점화식으로 해결할 수 있다. 만약 A[i]와 B[j](위는 오타임. i가 아니라 j임.)이 같았다면 LCS[i-1, j-1]의 값에 1을 더한 값을 LCS[i, j]에 쓰고, 그렇지 않은 경우에는 0을 쓴다. 만약 i=0이거나 j=0이면 가장 앞인 null문자와 비교했다는 것으로 0을 반환하면 된다.

 

4. Reference

가장 긴 공통 부분 문자열 (LCS - Longest Common Substring) 알고리즘