Longest Common Subsequence

最长公共子序列

首先要明确的是子序列的概念，注意啦，子序列不等于子串。子序列是一个字符串S去掉零个或者多个字符后所剩下的字符串就叫做子序列。

最长公共子序列的意思就是寻找两个给定字符串的的子序列，该子序列在两个字符串中以相同的次序出现，但是不一定是连续的。（连续的那是子串）

例如序列X=ABCBDAB，Y=BDCABA。序列BCA是X和Y的一个公共子序列，但是不是X和Y的最长公共子序列，子序列BCBA是X和Y的一个LCS，序列BDAB也是。

解题思路：DP

设输入字符串x和y的长度分别是：m和n，表示为:x[0..m-1]和y[0..n-1]。

L(X[0..m-1], Y[0..n-1]) 表示字符串x和y的最长公共子序列：

• 如果x的最后一个字符等于y的最后一个字符：x[m-1]=y[n-1],那么L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])
• 如果x的最后一个字符不等于y的最后一个字符：x[m-1]！=y[n-1],那么L(X[0..m-1], Y[0..n-1]) = max(L(X[0..m-2], Y[0..n-1]),L(X[0..m-1], Y[0..n-2]));

初始条件：

合法状态的初始值为当序列X的长度为0或Y的长度为0，公共子序列L长度为0

 public int longestCommonSubsequence(String x, String y) {
    if(x==null || x.length()==0 || y== null || y.length()==0)
        return 0;

    int m = x.length();
    int n = y.length();
    int[][] lcs = new int[m+1][n+1];

    /* lcs[0-m][0] & dp[0][0-n] 都已初始化0 */
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j) {
            if(x.charAt(i-1) == y.charAt(j-1)) {
                lcs[i][j] = lcs[i-1][j-1] + 1;
            }else  {
                lcs[i][j] = Math.max(lcs[i-1][j],lcs[i][j-1]);
            }
        }

    System.out.println(getLcs(x,y,lcs));
    return lcs[m][n];
}

public String getLcs(String a,String b,int[][] lcs) {
    StringBuilder sb = new StringBuilder();

    int i = a.length();
    int j = b.length();
    while (i > 0 && j > 0) {
        if (a.charAt(i-1) == b.charAt(j-1) && lcs[i][j] == lcs[i-1][j-1] + 1) {
            sb.append(a.charAt(i - 1));
            i--;
            j--;
        } else if (a.charAt(i-1) != b.charAt(j-1) && lcs[i-1][j] > lcs[i][j-1])
            i--;
        else
            j--;
    }
    return sb.reverse().toString();
}