【LCS】LCS问题有两种，一是最长公共子序列, 二是最长公共子串，两者的区别是子序列的每个元素在原集合中不必是紧邻的，只要保持相对位置即可，而子串的每个元素在原集合中必须是紧邻的，比如：集合A { 4 5 7 5 9 3 2 3 1 9 }， 集合B { 1 2 5 7 2 }，则集合A，B的最长公共子序列是{ 5 7 2 }，最长公共子串是{ 5 7 }。LCS是可以用动态规划求解的经典问题。
引申问题： 最长递增子串，最大子串和，最大子串积 （类似最大子串和，不过需要考虑符号问题）
示例代码
import java.util.Random;
class LCS {private static void printArray(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0;
i < arr.length;
i++) {
sb.append(arr[i]);
sb.append(' ');
}
sb.append('\n');
System.out.print(sb.toString());
}private static void fillArray(int[] arr) {
final int MAX = 10;
Random rand = new Random();
for (int i = 0;
i < arr.length;
i++) {
arr[i] = rand.nextInt(MAX);
}
}// 最长公共子序列
private static int lcs(int i, int j, int[] ai, int[] aj, int[][] dtRecord) {
if (i < 0 || j < 0) {
return 0;
}
if (dtRecord[i][j] >= 0) {
return dtRecord[i][j];
}
if (i == 0 && j == 0) {
return ai[i] == aj[j] ? 1 : 0;
}
if (ai[i] == aj[j]) {
dtRecord[i][j] = lcs(i - 1, j - 1, ai, aj, dtRecord) + 1;
} else {
dtRecord[i][j] = Math.max(lcs(i - 1, j, ai, aj, dtRecord), lcs(i, j - 1, ai, aj, dtRecord));
}
return dtRecord[i][j];
}// 最长公共子串
private static void lcs2(int[] ai, int[] aj) {
int endI = -1;
int endJ = -1;
int maxLength = 0;
int[][] dt = new int[ai.length][aj.length];
for (int i = 0;
i < ai.length;
i++) {
dt[i][0] = ai[i] == aj[0] ? 1 : 0;
if (dt[i][0] > maxLength) {
endI = i;
endJ = 0;
maxLength = dt[i][0];
}
}
for (int j = 0;
j < aj.length;
j++) {
dt[0][j] = aj[j] == ai[0] ? 1 : 0;
if (dt[0][j] > maxLength) {
endI = 0;
endJ = j;
maxLength = dt[0][j];
}
}
for (int i = 1;
i < ai.length;
i++) {
for (int j = 1;
j < aj.length;
j++) {
dt[i][j] = ai[i] == aj[j] ? dt[i-1][j-1] + 1 : 0;
if (dt[i][j] > maxLength) {
endI = i;
endJ = j;
maxLength = dt[i][j];
}
}
}
System.out.println("LCS2=" + maxLength + " endI=" + endI + " endJ=" + endJ);
}public static void main(String[] argv) {
final int row = 5;
final int column = 10;
int[] x = new int[column];
int[] y = new int[row];
fillArray(x);
printArray(x);
fillArray(y);
printArray(y);
int[][] dt = new int[row][column];
for (int i = 0;
i < row;
i++) {
for (int j = 0;
j < column;
j++) {
dt[i][j] = -1;
}
}
System.out.println("LCS = " + lcs(row - 1, column - 1, y, x, dt));
lcs2(x, y);
}
}
参考阅读 动态规划算法之最长公共子序列&最长公共子串
程序员面试100题之最长公共子串
