最长公共子序列（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、特点及解决方法
特点：分析是从大到小，写代码是从小到大。
计算过程中会把结果都记录下，最终结果在记录中找到。
解决方法：
- 穷举法（实际应用中不可取）
- 动态规划法
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