最长公共子序列

作者: Mereder | 来源:发表于2019-04-29 16:40 被阅读0次

公共子序列问题
最长公共子序列和最长公共子串
算法(04)动态规划
LCS问题
子序列问题
子串子序列总结
序列比对（二十四）——最长公共子序列
lintcode 最长公共子序列
字符串的几个问题
算法问题清单

动态规划合集：

1.矩阵链乘法
 2.投资组合问题
 3.完全背包问题
 4.01背包问题
 5.最长公共子序列

例题5——最长公共子序列

描述

给定序列
$X=<x_1,x_2,x_3,\cdots,x_n> \\ Y=<y_1,y_2,y_3,\cdots,y_m>$
求X和Y的最长公共子序列。
实例：
X：A B C B D A B
Y：B D C A B A
最长公共子序列为：BCBA，长度为4

问题分析

以 $X=<x_1,x_2,\cdots,x_n>,Y=<y_1,y_2,\cdots,y_m>,Z=<z_1,z_2,\cdots,z_k$ 做一般性说明，其中Z表示XY的最长公共子序列，一定有下述条件：

①若 $x_n = y_m \rightarrow z_k=x_n=y_m$ ,且 $Z_{k-1}$ 是 $X_{n-1},Y_{m-1}$ 的LCS。

②若 $x_n \ne y_m,x_n\ne z_k$ , $Z$ 是 $X_{n-1}$ 与 $Y_m$ 的LCS。

③若 $x_n \ne y_m,y_m\ne z_k$$Z$ 是 $X_{n}$ 与 $Y_{m-1}$ 的LCS。

令 $C[i,j]$ 表示 $X_i与Y_j$ 的LCS的长度，那么递推表达式可以写成：

$C[i,j] = \begin{cases} 0 & i=0 或\quad j=0 \\ C[i-1,j-1]+1 & i,j>0, \quad x_i=y_j \\ max\{C[i,j-1],C[i-1,j]\} & i,j>0,\quad x_i \ne y_j \end{cases}$

标记函数为：
$B[i,j]=\begin{cases} \nwarrow & if \quad C[i,j] = C[i-1,j-1]+1 \\ \uparrow & if \quad C[i,j] = C[i-1,j] \\ \leftarrow & if \quad C[i,j] = C[i,j-1] \end{cases}$

标记函数走法

算法实现

public class LongestCommonSubsequence {
    public static int [][]mem;
    public static int [][]s;
    public static int [] result; // 记录子串下标
    public static int LCS(char []X,char []Y,int n,int m){
        for (int i = 0; i <= n; i++) {
            mem[i][0] = 0;
            s[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            mem[0][i] = 0;
            s[0][i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m ; j++) {
                if (X[i-1] == Y[j-1]){
                    mem[i][j] = mem[i-1][j-1] + 1;
                    s[i][j] = 1;
                }
                else {
                    mem[i][j] = Math.max(mem[i][j-1],mem[i-1][j]);
                    if (mem[i][j] == mem[i-1][j]){
                        s[i][j] = 2;
                    }
                    else s[i][j] = 3;
                }
            }
        }
        return mem[n][m];
    }
    // 追踪解
    public static void trace_solution(int n,int m){
        int i = n;
        int j = m;
        int p = 0;
        while (true){
            if (i== 0 || j == 0) break;
            if (s[i][j] == 1 ){
                result[p] = i;
                p++;
                i--;j--;
            }
            else if (s[i][j] == 2){
                i--;
            }
            else { //s[i][j] == 3
                j--;
            }
        }

    }
    public static void print(int [][]array,int n,int m){
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                System.out.printf("%d ",array[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char []X = {'A','B','C','B','D','A','B'};
        char []Y = {'B','D','C','A','B','A'};
        int n = X.length;
        int m = Y.length;
        // 这里重点理解，相当于多加了第一行 第一列。
        mem = new int[n+1][m+1];
        // 1 表示 左上箭头  2 表示 上  3 表示 左
        s = new int[n+1][m+1];
        result = new int[Math.min(n,m)];
        int longest = LCS(X,Y,n,m);
        System.out.println("备忘录表为：");
        print(mem,n,m);
        System.out.println("标记函数表为：");
        print(s,n,m);
        System.out.printf("longest : %d \n",longest);

        trace_solution(n,m);
        // 输出注意  result 记录的是字符在序列中的下标
        for (int k = longest-1; k >=0 ; k--) {
            // 还需要再减一 才能跟 X Y序列对齐。
            int index = result[k]-1;
            System.out.printf("%c ",X[index]);
        }

    }
}