如何将最长公共子序列算法修改为最长公共连续子序列算法

Question

我想知道如何更改我的类，使其能够在两个字符串之间产生最长的连续公共子序列。这段代码现在已经设置好了，这样我就可以获得这两个字符串中最长公共子序列的长度。我希望最终结果字符串是完整的(它可以在两个字符串中找到，中间没有字符(。例如，我希望发送方法ACGGTTGTCGCAGTCC和TGTAGCAG会导致GCAG的长度为4，而不是现在的情况，即TGTGCAG的长度为7。

public class GenomeSequencer {
private String x;
private String y;
public String getLongestCommon() {
int[][] table = lcsLength();
return Integer.toString(table[x.length()][y.length()]);
}
private int[][] lcsLength() {
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 j = 0; j <= n; j++) {
c[0][j] = 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 if (c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
} else {
c[i][j] = c[i][j - 1];
}
}
}
return c;
}
}

Answer 1

如果您真的想重用旧的解决方案，请考虑为什么它不再工作。

在这三个转换中，字母相等的一个应该保留，跳过其中一个字符串中字母的两个应该消失。

因此，转换可以只是：

if (x.charAt(i - 1) == y.charAt(j - 1)) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = 0;
}

注意，使用这种方法，答案不再是c[m][n]：相反，您应该在整个表中搜索最大值。

---

转换的简单性表明，对于最长的公共子串问题(子串是连续的子序列(有更快的解决方案。事实上，有一个线性但复杂的解决方案涉及后缀树(在上面的链接中提到(，或者使用哈希和二进制搜索答案长度的更简单的解决方案。