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

Question

我想知道如何更改我的 class 以便它可以在两个字符串之间生成最长的连续公共子序列。现在设置此代码，以便我可以获得两个字符串的最长公共子序列的长度。我希望最终结果字符串是完整的（它可以在两个字符串中找到，中间没有字符）。例如，如果发送方法 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]：相反，您应该搜索整个 table 以获取最大值。

转换的简单性表明 longest common substring 问题有更快的解决方案（子字符串是连续的子序列）。事实上，有一个涉及后缀树的线性但复杂的解决方案（在上面 link 中提到），或者使用哈希和二进制搜索答案长度的更简单的解决方案。

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

How to modify a longest common subsequence algorithm to a longest common contiguous subsequence algorithm?

java

dynamic-programming

subsequence