问题描述
- 子序列
X=(ABCBDAB) X的子序列是下标递增的X的字符组成的序列,但是不一定连续,如:ABCD,ACDAB等都是其子序列,而 ADC不是子序列 - 最长公共子序列
如果Z既是X的子序列,又是Y的子序列,那么Z是X与Y的公共子序列,其中最长Z就是最长公共子序列 - 序列相似度
该问题用来描述两个序列的相似度,当然相似度还有其他描述方法
- X是Y的子串
- X转换为Y的操作最少
- X与Y的最大公共字串
求解
暴力求解
分别求出X,Y的所有子序列,然后求所有公共子序列,取其中长度最大的,由于求所有自序列复杂度为2^m,时间复杂度为指数型
动态规划
原理:
X={x1,x2...xn}
Y={y1,y2...ym}
他们最长公共子序列为Z
如果 xm=yn,则Zk=xm=yn,Zk-1是Xm-1 与 Yn-1的最长公共子序列
如果xm!=yn,若Zk!=xm,则Z是Xm-1和Yn的最大公共子序列
如果xm!=yn,若Zk!=yn,则Z是Xm和Yn-1的最大公共子序列
代码
- 如果只求长度,可以用一维数组迭代求解
- 如果求具体序列,需要用二维数组来记录求解路径
public class LongestCommonSequence {
public static void main(String[] args) {
String X = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";
String Y = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";
String C = "GTCGTCGGAAGCCGGCCGAA";
System.out.println(longestCommonSequence(X, Y).equals(C));
System.out.println(longestCommonSequenceLength(X, Y));
}
public static int longestCommonSequenceLength(String X, String Y) {
int m = X.length();
int n = Y.length();
int[] c = new int[m + 1];
for (int i = 0; i <= m; i++) {
c[i] = 0;
}
for (int i = 1; i <= n; i++) {
int leftUp = 0;
for (int j = 1; j <= m; j++) {
int temp = leftUp;
leftUp = c[j];
if (X.charAt(j - 1) == Y.charAt(i - 1)) {
c[j] = temp + 1;
} else {
c[j] = Math.max(c[j - 1], c[j]);
}
}
}
return c[m];
}
public static String longestCommonSequence(String X, String Y) {
int m = X.length();
int n = Y.length();
int[][] c = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
c[i][0] = 0;
}
for (int i = 0; i <= n; i++) {
c[0][i] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
}
}
}
StringBuilder sb = new StringBuilder();
while (m > 0 && n > 0) {
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
sb.append(X.charAt(m - 1));
m--;
n--;
} else if (c[m - 1][n] >= c[m][n - 1]) {
m--;
} else {
n--;
}
}
return sb.reverse().toString();
}
}