【算法设计与分析】最长公共子序列 (JAVA代码实现及实现)——动态规范

问题描述

设序列 X, Z,

​

若存在 一个严格递增下标序列

使得

则称 Z 是 X 的子序列，子序列所包含的元素个数称为子序列的长度。

如果Z既是 X的子序列又是Y的子序列，则称Z为X 与 Y 的公共子序列。

最长公共子序列(Longest Common Subsequence,LCS)

给定序列

求 X 和 Y 的最长公共子序列

为了后续讨论的方便，引入一个符号：

假定

，采用

表示X 的前i个元素组成的子序列。显然：

递归地定义最优值

递归地定义最优值.png

求最长公共子序列

X={a,c,a,c,b}

Y={a,b,c,b,c}

过程.jpg

说明：1：计算次序：或逐行，或逐列，(本例采用逐行方式)

JAVA代码实现

package cn.fyfye.algorithm.test;

public class LCS {

    public static void main(String[] args) {
//        X
        StringBuilder x = new StringBuilder("acacb");
//        Y
        StringBuilder y = new StringBuilder("abcbc");

        int[][] c = new int[x.length()+1][y.length()+1];
        int[][] b = new int[x.length()+1][y.length()+1];

        for(int i=0;i<c.length;i++){
            for (int j=0;j<c[i].length;j++){
                if(i==0 || j==0) {
                    c[i][j]=b[i][j]=0;
                }else if(x.charAt(i-1)==y.charAt(j-1)){
                    c[i][j]=c[i-1][j-1]+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;
                }else{
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
        }
        System.out.println("--------------------------c---------------------------");
        pr(c);
        System.out.println("------------------------------------------------------");
        System.out.println("--------------------------b---------------------------");
        pr(b);
        System.out.println("------------------------------------------------------");

        StringBuilder son = new StringBuilder("");
//        递归找最长公共子序列
        subsequence(x,b,b.length-1,b[b.length-1].length-1,son);
        System.out.println(x+"与"+y+"的最长公共子序列为:"+son);


    }
    public static void subsequence(StringBuilder s,int [][] b,int i,int j,StringBuilder son){
        if( i < 1 || j < 1){
            return;
        }
        if(b[i][j]==1){
            son.insert(0,s.charAt(i-1));
            subsequence(s,b,i-1,j-1,son);
        }else if(b[i][j]==2){
            subsequence(s,b,i-1,j,son);
        }else{
            subsequence(s,b,i,j-1,son);
        }
    }


    /**
     * 打印
     * @param a 数组
     */
    public static void pr(int[][] a){
        for(int i=1;i<a.length;i++){
            for (int j=1;j<a[i].length;j++){
                System.out.print(a[i][j]+"\t");
            }
            System.out.println();
        }
    }
}

运行截图.png

注:代码仅供参考，还有其他方式

作者QQ：420318184
邮箱:fy@0fy0.com