📌 About

LCS algorithm은 두 가지로 해석이 된다. Longest Common Subsequence와 Longest Common Substring이다. Subsequence은 문자열의 부분 문자열들의 조합이 가장 길게 같은 두 문자열의 공통 부분을 이야기 한다. Substring은 문자열의 한 부분 문자열이 가장 길게 같은 두 문자열의 공통 부분을 이야기한다. 일반적으로는 subsequence를 이야기한다.

📌 Algorithm

📍 Longest Common Subsequence

Step 0. 문자열 A와 문자열 B의 길이에 따라 LCS 배열을 생성

private final String strA;
private final String strB;

private int[][] lcs;

private void initializeLCSArray() {
    lcs = new int[strA.length() + 1][strB.length() + 1];
}

Step 1. 문자열 A와 문자열 B를 앞에서부터 한 문자씩 비교

Step 1-1. 두 문자가 다르다면 LCS[i - 1][j], LCS{i][j - 1] 중 큰값을 저장

Step 1-2. 두 문자가 같다면 LCS[i - 1][j - 1] + 1 저장

private void compareChars() {
    for (int i = 1; i <= strA.length(); i++)
        for (int j = 1; j <= strB.length(); j++)
            lcs[i][j] = strA.charAt(i - 1) == strB.charAt(j - 1) ?
                    lcs[i - 1][j - 1] + 1 :
                    Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}

Step 2. 공통 부분 문자열 찾기 (0으로 이동하면 종료)

Step 2-1. LCS 배열의 마지막 값부터 탐색

Step 2-2. LCS[i - 1][j]와 LCS[i][j _ 1] 중 같은 값이 있으면 해당 값으로 이동

Step 2-3. 같은값이 없으면 문자를 공통 부분에 추가하고 i - 1, j - 1 이동

private String findCommonString() {
    StringBuilder builder = new StringBuilder();
    int i = strA.length();
    int j = strB.length();
    while (lcs[i][j] != 0) {
        if (lcs[i - 1][j] == lcs[i][j]) i--;
        else if (lcs[i][j - 1] == lcs[i][j]) j--;
        else {
            builder.append(strA.charAt(i - 1));
            i--;
            j--;
        }
    }
    return builder.reverse().toString();
}

📍 Longest Common Substring

LCS(Substring)은 LCS(Subsequence)에서 두 문자가 다를 때만 0으로 저장하면 된다.

추가로 substring은 최장 길이 탐색을 하면서 동시에 최장 공통 문자열을 구할 수 있다.

private String compareSubstringChars() {
    String common = "";
    for (int i = 1; i <= strI.length(); i++) {
        for (int j = 1; j <= strJ.length(); j++) {
            if (strI.charAt(i - 1) == strJ.charAt(j - 1)) {
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                String string = strI.substring(i - lcs[i][j], i);
                if (common.length() < string.length()) common = string;
            }
        }
    }
    return common;
}

📌 Java Code

📍 Longest Common Subsequence

public class LCS {

    private final String strA;
    private final String strB;

    private int[][] lcs;

    public LCS(String strA, String strB) {
        this.strA = strA;
        this.strB = strB;
    }

    public String runSubsequence() {
        initializeLCSArray();
        compareChars();
        return findCommonString();
    }

    private void initializeLCSArray() {
        lcs = new int[strA.length() + 1][strB.length() + 1];
    }

    private void compareChars() {
        for (int i = 1; i <= strA.length(); i++)
            for (int j = 1; j <= strB.length(); j++)
                lcs[i][j] = strA.charAt(i - 1) == strB.charAt(j - 1) ?
                        lcs[i - 1][j - 1] + 1 :
                        Math.max(lcs[i - 1][j], lcs[i][j - 1]);
    }

    private String findCommonString() {
        StringBuilder builder = new StringBuilder();
        int i = strA.length();
        int j = strB.length();
        while (lcs[i][j] != 0) {
            if (lcs[i - 1][j] == lcs[i][j]) i--;
            else if (lcs[i][j - 1] == lcs[i][j]) j--;
            else {
                builder.append(strA.charAt(i - 1));
                i--;
                j--;
            }
        }
        return builder.reverse().toString();
    }
}

📍 Longest Common Substring