最长公共子序列

2018-05-04

最长公共子序列问题-LCS问题

问题描述：

给定两个序列 X={x1,x2,x3,…,xm}和Y={y1,y2,…,yn}，求X和Y长度最长的公共子序列。

求解思路：

寻找特征:

LCS问题具有最优子结构性质。可以将子问题对应两个输入序列的前缀对。

令Z = {z1,z2,…,zk}，为X和Y的任意LCS。有如下性质，

1.1 如果xm = yn,则zk = xm = yn 且Zk-1是Xm-1和Yn-1的一个LCS。

1.2 如果xm不等于yn，那么zk不等于xm意味着Z是Xm-1和Y的一个LCS。

1.3 如果xm不等于yn，那么zk不等于yn意味着Z是Xm和Yn-1的一个LCS。
设计递归公式

根据上面的特征，可以知道要求解Xn和Ym的一个LCS时，我们需要求解一个或两个子问题。如果xm=yn，我们应该求解Xm-1和Yn-1的一个LCS。如果xm不等于yn，就必须求解两个子问题：求Xm-1和Y的一个LCS与X和Yn-1的一个LCS。其中较长的一个即为X和Y的一个LCS。

可以用一个二维数组C来储存Xi和Yi的LCS长度，可以得到如下公式：
优化

这里对与这个问题可以使用动态数组的方法，将C[i,j]自底向上的计算出来，最终求得C[m,n],也就是Xm和Yn的最大公共子序列。但是通过观察上面那个公式，我们可以发现要计算C[i, j]只需计算C[i-1,j-1]或者C[i-1,j]和C[i,j-1]。而无需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]。

所以我们可以采用自顶而下的方法，需要用到哪个再去计算那个，这样可以减小计算量。也被称作为备忘录方法
算法描述

首先将C[i,0],C[0,j]初始化为0。其余m×n个C[i,j]全部初始化为-1。

计算C[i,j]的递归算法LCS(X,Y, i,j,C)：

若x[i]=y[j]，则去检查C[i-1,j-1]，若C[i-1,j-1]> -1（已经计算出来），就直接把C[i-1,j-1]+1赋给C[i,j]。若C[i-1,j-1]=-1（尚未计算出来），就递归调用LCS(X,Y, i-1,j-1,C) 计算出C[i-1,j-1]，然后再把C[i-1,j-1]+1赋给C[i,j] 。

若x[i] != y[j]，则要检查C[i-1,j]和C[i,j-1]。若两者均 > -1（已经计算出来），则把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]。若C[i-1,j], C[i,j-1] 两者中有一个等于-1（尚未计算出来），或两者均等于-1，就递归调用LCS将其计算出来，然后再把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]。

实现代码

/**
 * com.mogujie.ACM
 * 最长公共子序列问题-LCS问题
 * <p>
 * 问题描述：给定两个序列 X={x1,x2,x3,…,xm}和Y={y1,y2,…,yn}，求X和Y长度最长的公共子序列。
 *
 * @author muzhi
 * 2018/5/4
 */
public class LongestCommonSubsequence {

    /**
     * 解题思路：
     * LCS问题具有最优子结构性质。可以将子问题对应两个输入序列的前缀对。
     * 令Z = {z1,z2,…,zk}，为X和Y的任意LCS。有如下性质，
     * 1.1 如果xm = yn,则zk = xm = yn 且Zk-1是Xm-1和Yn-1的一个LCS。
     * 1.2 如果xm不等于yn，那么zk不等于xm意味着Z是Xm-1和Y的一个LCS。
     * 1.3 如果xm不等于yn，那么zk不等于yn意味着Z是Xm和Yn-1的一个LCS。
     * 因此，最大子序列就是计算
     */
    public static void LCS(char[] x, char[] y, int i, int j, int[][] c) {
        if (i == 0 || j == 0) {
            return;
        }

        if (x[i] == y[j]) {
            // 说明还没有计算出来
            if (c[i - 1][j - 1] == -1) {
                LCS(x, y, i - 1, j - 1, c);
            } else {
                c[i][j] = c[i - 1][j - 1] + 1;
            }
        } else {
            if (c[i][j - 1] == -1) {
                LCS(x, y, i, j - 1, c);
            }

            if (c[i - 1][j] == -1) {
                LCS(x, y, i - 1, j, c);
            }

            c[i][j] = c[i][j - 1] > c[i - 1][j] ? c[i][j - 1] : c[i - 1][j];
        }
    }

    public static int doSoult(String x, String y) {
        int xSize = x.length();
        int ySize = y.length();

        int[][] c = new int[xSize + 1][ySize + 1];
        // 初始化c的值为-1
        for (int i = 1; i <= xSize; i++) {
            for (int j = 1; j <= ySize; j++) {
                c[i][j] = -1;
            }
        }

        char[] xCharArray = new char[xSize + 1];
        xCharArray[0] = '#';
        char[] yCharArray = new char[ySize + 1];
        yCharArray[0] = '#';

        System.arraycopy(x.toCharArray(), 0, xCharArray, 1, xSize);
        System.arraycopy(y.toCharArray(), 0, yCharArray, 1, ySize);

        LCS(xCharArray, yCharArray, xSize, ySize, c);
        return c[xSize][ySize];
    }

    public static void main(String[] args) {

        String x = "abcderg";
        String y = "abc";
        System.out.println(doSoult(x, y));
    }
}