最长公共子序列

问题描述

给定两个序列X=｛A,B,C,B,D,A,B｝和Y={B,D,C,A,B,A}，当另一序列Z={B,D}既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。Z={B,C,B,A}是比{B,D}更长的子序列，它的长度为4，因为X和Y没有长度大于4的公共子序列，所以Z ={B,C,B,A}是X和Y的最长公共子序列。

最长公共子序列问题（Longest Common Subsequence, LCS）：给定两个序列X={x1, x2, …, xm}和Y={y1, y2, …, yn}，找出X和Y的最长公共子序列Z={z1, z2, …, zk} 。

解决方案

1.找出最长公共子序列问题最优解性质，并刻划其结构特征。
1)若xm=yn = zk，则Zk-1是Xm-1和Yn-1的最长公共子序列。
2)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列。
3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列。

  1. 子问题的递归结构
    由最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。其它情况下，由最优子结构性质可建立递归关系如下：
    图片说明
  1. 计算最优值 
package dynamic;
/* 
 * 给定x[0:m]和y[0:n]字符序列，求两者的最长公共子序列，公共子序列长度记录在二维数组c[0:m][0:n]内,
 * 则最长为c[m][n]，最优解的寻找轨迹记录在二维数组b[0:m][0:n]内，通过对应x的下标，将公共子序列输出
 * 递归的出口在i=0或y=0
 * c[i][j]下标从1开始
 * x[i],y[j]下标从0开始，所以遍历x,y时，x[i-1],y[j-1]表示
 */
public class Longest_common_subsqence {

    public static int lcsLength(char[] x,char[] y,int[][] b) {
        //x,y为给定的字符序列，b用来记录公共子序列的寻找轨迹
        int m=x.length;
        int n=y.length;
        int[][] c=new int[m+1][n+1];//将当前位置的公共子序列长度情况，结果记录在表格里，行列数加1用来保存0
        for(int i=0;i<=m;i++) {c[i][0]=0;} //如果y为空序列，那么他们的公共子序列也为空序列
        for(int j=0;j<=n;j++) {c[0][j]=0;} //如果x为空序列，那么他们的公共子序列也为空序列
        for(int i=1;i<=m;i++) //当x和y都不为空序列时，开始遍历各自每一个是否相同
            for(int j=1;j<=n;j++) {
                if(x[i-1]==y[j-1]) { //如果x和y中有相同的元素，那么最长公共子序列长度加1
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;  //b[i][j]=1代表两元素相同，方便记录最优解
                }
                else
                    if(c[i-1][j]>=c[i][j-1]) { //如果当前位置的上面的元素大于等于它左边的元素，
                        c[i][j]=c[i-1][j];    //那么这个位置的值为上面元素的值所表示的公共子序列长度
                        b[i][j]=2;  //b[i][j]=2代表上面元素所代表的长度大于等于左边元素所代表的长度
                    }
                    else {                  //如果当前位置的上面元素小于它的左边元素，
                        c[i][j]=c[i][j-1];  //那么这个位置的值为左边元素的值所代表的公共子序列长度
                        b[i][j]=3;  //b[i][j]=3代表左边元素所代表的长度大于上面元素所代表的长度
                    }
            }
        return c[m][n];  //当遍历到二维表格的最后位置时，此时的值即为最长公共子序列    
    }

    public static void lcs(int i,int j,char[] x,int[][] b) { //lcs方法用来输出最优解，即最长公共子序列
        if(i==0||j==0) return;//递归的出口
        if(b[i][j]==1) {
            lcs(i-1,j-1,x,b);  //c[i][j]=c[i-1][j-1]+1
            System.out.println(x[i-1]); //输出当前位置的相同字符
        }
        else if(b[i][j]==2) lcs(i-1,j,x,b); //c[i][j]=c[i-1][j]
        else lcs(i,j-1,x,b); //c[i][j]=c[i][j-1]

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        char[] x= {'A','B','C','B','D','A','B'};
        char[] y= {'B','D','C','A','B','A'};
        int[][] b=new int[x.length+1][y.length+1]; //行列数都各自加1，因为需要给空序列留一个位置来表示
        lcsLength(x,y,b);
        lcs(x.length,y.length,x,b);

    }

}

4.演算过程
图片说明

反思总结

一开始代码打好以后，发现总是报数组越界的错误，先是发现c[i][j]和b[i][j]的行列数要比x[]和y[]多1，来保存空序列，但是为了一致性，x和y的下标要从c,b下标减1表示。

这道题的解法通过用b[][]来记录演算轨迹，不同的值表示不同的情况，遇到1就根据i-1的值从x[]中将公共序列输出。

tip

图片说明