最长公共子序列LCS

[qjkobe]

子序列

不多解释了看例子就懂：
<A,B,C,D,E,F,G>的子序列有:<B,C,D>, <A,C,E,G>等。

公共子序列

一个序列，是另外两个序列的子序列，那么这个序列就是那两个序列的公共子序列。如果没有比他更长的公共子序列，那他就是最长公共子序列。

LCS

求两个序列的最长公共子序列（算法导论第三版15.4章222页）

[qjkobe]

动态规划

完全按照算法导论实现了一版代码。详情参考算法导论15.4章。或看注释

public class LCS {
    public static void LCSLength(char[] X, char[] Y, int[][] b, int[][] c) {
        int m = X.length - 1;
        int n = Y.length - 1;
        //当一个序列为0，那么最长子序列为0
        for (int i = 1; i <= m; i++) {
            c[i][0] = 0;
        }
        for (int j = 0; j <= n; j++) {
            c[0][j] = 0;
        }
        //上箭头是1，左箭头是2，左上箭头是3
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X[i] == Y[i]) {
                    //因为最后一个字符相等，所以去掉最后一个字符的最长子序列的长度+1就是当前最长子序列
                    c[i][j] = c[i - 1][j - 1] + 1;
                    //此时往动态规划矩阵左上方走
                    b[i][j] = 3;
                } else if (c[i - 1][j] >= c[i][j - 1]) {
                    //如果最后一个字符不一样，那最后一个字符就不影响判断最长子序列。
                    c[i][j] = c[i - 1][j];
                    b[i][j] = 1;
                } else {
                    c[i][j] = c[i][j - 1];
                    b[i][j] = 2;
                }
            }
        }
    }

    public static void PrintLCS(int[][] b, char[] X, int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }
        if (b[i][j] == 3) {
            //只有斜线，也就是当前字符相等的时候，才会被打印出来。
            PrintLCS(b, X, i - 1, j - 1);
            System.out.print(X[i]);
        } else if (b[i][j] == 1) {
            PrintLCS(b, X, i - 1, j);
        } else {
            PrintLCS(b, X, i, j - 1);
        }
    }

    public static void main(String[] args) {
        //为了动态规划方便，X的最前面插入一个空白
        char[] X = {' ', 'A', 'B', 'C', 'D', 'E', 'F'};
        char[] Y = {' ', 'A', 'C', 'C', 'F', 'E', 'F'};
        //答案应该是ACEF
        int[][] b = new int[X.length][Y.length];
        int[][] c = new int[X.length][Y.length];
        LCSLength(X, Y, b, c);
        PrintLCS(b, X, X.length-1, Y.length-1);
    }
}

[qjkobe]

因为b数组由c唯一决定，所以不用b数组，靠判断c也是可以的。

    public static void PrintLCS2(int[][] c, char[] X, int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }
        if (c[i][j] == c[i - 1][j - 1] + 1) {
            //只有斜线，也就是当前字符相等的时候，才会被打印出来。
            PrintLCS2(c, X, i - 1, j - 1);
            System.out.print(X[i]);
        } else if (c[i][j] == c[i - 1][j]) {
            PrintLCS2(c, X, i - 1, j);
        } else {
            PrintLCS2(c, X, i, j - 1);
        }
    }