Longest common Subsequence vs Longest common Substring

這兩題很像! 但不一樣，subsequence可以不連續，substring 則是要求連續的字串

subsequence 的分析為:

兩個 string A, B, 可以分別拆成 A = sub1 + e1, B = sub2 + e2

這時分成2種 case:

1. e1 = e1, LCS(A, B) = LCS(sub1, sub2) + 1
2. e1 != e2, LCS(A, B) = LCS(A, sub2) or LCS(sub1, B) or LCS(sub1, sub2)

=>

LCS(A, B) =

Max{ LCS(A, sub2), LCS(sub1, B) } , when e1 != e2,

LCS(sub1, sub2) + 1, when e1 = e2

用個二維陣列初始 f[i][j] 表示 A(1~i) 這個字串和 B(1~j) 這個字串的目前最長 LCS

答案就是求 f[A.length()][B.length()]

 public int longestCommonSubsequence(String A, String B) {
    if (A == null || B == null 
        || A.length() == 0 || B.length() == 0) {
        return 0;
    }


    int aLen = A.length(), bLen = B.length();
    int[][] f = new int[aLen+1][bLen+1];
    f[0][0] = 0;
    f[1][0] = 0;
    f[0][1] = 0;

    for (int i=1; i<aLen+1; i++) {
        for (int j=1; j<bLen+1; j++) {
            if (A.charAt(i-1) == B.charAt(j-1)) {
                f[i][j] = 1 + f[i-1][j-1];
            } else {
                f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
            }
        }
    }
    return f[aLen][bLen];
}

substring 分析為:

兩個 string A, B, 可以分別拆成 A = sub1 + e1, B = sub2 + e2

這時分成2種 case:

1. e1 = e2, LCS(A, B) = LCS(sub1, sub2) + 1 => 這個字元相同才有可能是 substring
2. e1 != e2, LCS(A, B) = LCS(sub1, sub2) = 0 => 這個字元不同，不可能是 substring

上面方程可以這樣想，我們以 f[i][j] 表示 A(1~i) 這個字串和 B(1~j) 這個字串的目前最長 LCS

當 e1 = e2, f[i][j] = f[i-1][j-1] + 1，這沒問題，因為此字元相同

當 e1 != e2, 表示此字元不同，那麼 A(1~i), B(1~j) 的 LCS, 也就是 f[i][j] 要為 0，因為這個狀況下是不會有 LCS 的

也不需要跟前面的取 MAX 什麼的，因為此字元就不同了阿! 跟 subsequence 是不同的

那問題來了，既然不能跟前面的取 MAX，答案就不會是 f[A.length()][B.length()], 而是要遍歷 f

public int longestCommonSubstring(String A, String B) {
    // state: f[i][j] is the length of the longest lcs
    // ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
    int n = A.length();
    int m = B.length();
    int[][] f = new int[n + 1][m + 1];

    // initialize: f[i][j] is 0 by default

    // function: f[i][j] = f[i - 1][j - 1] + 1 or 0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = 0;
            }
        }
    }

    // answer: max{f[i][j]}
    int max = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            max = Math.max(max, f[i][j]);
        }
    }

    return max;
}