最长公共子序列（Longest Common Subsequenen, LCS）

1、概念

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

2、定义

一个序列A任意删除若干个字符得到新序列B，则B叫做A的子序列。

两个序列X和Y的公共子序列中,长度最长的那个,定义为X和Y的最长公共子序列。

例如X={A,B,C,B,D,A,B}，Y={B,D,C,A,B,A}则它们的lcs是{B,C,B,A}和{B,D,A,B}。求出一个即可。

3、LCS的应用

相似度的比较: 计算生物学DNA对比(亲子验证)，百度云盘找非法数据(岛国片)。

图形相似处理，媒体流的相似比较，百度知道，百度百科，WEB页面中找非法言论。

4、特点及解决方法

特点：分析是从大到小，写代码是从小到大。

计算过程中会把结果都记录下，最终结果在记录中找到。

解决方法：

• 1. 穷举法（实际应用中不可取）
• 2. 动态规划法

5、算法分析

1. LCS的符号表示

字符串X,长度m,从1开始计数;

字符串Y,长度n,从1开始计数

LCS(X, Y)为字符串X和Y的最长公共子序列，其中的一个解为Z=<z1,z2,...zk>

注意:LCS(X,Y)其实为一个集合,Z为一个解

2. Xm = Yn

2.png 3.png

3. Xm != Yn

4.png 5.png 6.png

4. 代码分析与编码，规则：相同的取左上加1,不同取上和左中的最大值

1.png

6、代码实现

import java.util.Stack;

/**
 * 最长公共子序列
 * author: bobo
 * create time: 2018/12/27 1:54 PM
 * email: jqbo84@163.com
 */
public class LCS {

    /**
     * 比较大小，返回大的
     *
     * @param a
     * @param b
     * @return
     */
    public static int max(int a, int b) {
        return a > b ? a : b;
    }

    /**
     * 使用动态规划的方式填入数据
     *
     * @param x
     * @param y
     * @return
     */
    public static int[][] fillinLCS(String x, String y) {
        char[] s1 = x.toCharArray();
        char[] s2 = y.toCharArray();
        int[][] array = new int[x.length() + 1][y.length() + 1];
        //先把第一行和第一列填上零
        for (int i = 0; i < array[0].length; i++) {
            array[0][i] = 0;
        }
        for (int i = 0; i < array.length; i++) {
            array[i][0] = 0;
        }
        //使用动态规划的方式填入数据
        for (int i = 1; i < array.length; i++) {
            for (int j = 1; j < array[i].length; j++) {
                if (s1[i - 1] == s2[j - 1]) {//如果相等，左上角加1填入
                    array[i][j] = array[i - 1][j - 1] + 1;
                } else {//不等，取左和上的最大值
                    array[i][j] = max(array[i - 1][j], array[i][j - 1]);
                }
            }

        }
        return array;
    }

    /**
     * 从后往前找到最长公共子序列结果
     * @param x
     * @param y
     * @param left 表示当两个值相等当情况，true：取左边，false：取右边
     * @return
     */
    public static String getLCS(String x, String y, boolean left) {
        int[][] array = fillinLCS(x, y);
        Stack stack = new Stack();
        int i = x.length() - 1;
        int j = y.length() - 1;
        //从后往前找到结果
        while (i >= 0 && j >= 0) {
            if (x.charAt(i) == y.charAt(j)) {
                stack.push(x.charAt(i));
                i--;
                j--;
            } else {
                //注意数组和String中的位置有一位差
                if (array[i + 1][j + 1 - 1] > array[i + 1 - 1][j + 1]) {
                    if (left) j--;
                    else i--;
                } else {
                    if (left) i--;
                    else j--;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

}

7、测试及结果

@Test
public void testLCS() {
    int[][] array = LCS.fillinLCS("abcbdab", "bdcaba");
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            System.out.print(array[i][j] + "  ");
        }
        System.out.println();
    }

    System.out.println("---------------------------");

    String lcs = LCS.getLCS("abcbdab", "bdcaba", true);
    System.out.println("lcs = " + lcs);
}

结果：

0  0  0  0  0  0  0  
0  0  0  0  1  1  1  
0  1  1  1  1  2  2  
0  1  1  2  2  2  2  
0  1  1  2  2  3  3  
0  1  2  2  2  3  3  
0  1  2  2  3  3  4  
0  1  2  2  3  4  4  
---------------------------
lcs = bcba