【算法設(shè)計(jì)與分析】最長公共子序列 (JAVA代碼實(shí)現(xiàn)及實(shí)現(xiàn))——?jiǎng)討B(tài)規(guī)范

問題描述

設(shè)序列 X, Z,

?

若存在 一個(gè)嚴(yán)格遞增下標(biāo)序列

使得

則稱 Z 是 X 的子序列，子序列所包含的元素個(gè)數(shù)稱為子序列的長度。

如果Z既是 X的子序列又是Y的子序列，則稱Z為X 與 Y 的公共子序列。

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

給定序列

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

為了后續(xù)討論的方便，引入一個(gè)符號：

假定

，采用

表示X 的前i個(gè)元素組成的子序列。顯然：

遞歸地定義最優(yōu)值

遞歸地定義最優(yōu)值.png

求最長公共子序列

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

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

過程.jpg

說明：1：計(jì)算次序：或逐行，或逐列，(本例采用逐行方式)

JAVA代碼實(shí)現(xiàn)

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 數(shù)組
     */
    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();
        }
    }
}

運(yùn)行截圖.png

注:代碼僅供參考，還有其他方式

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