最长公共子序列（LCS）蛮力算法

Question

我想创建一种蛮力算法来找到2个字符串之间最大的公共子序列，但是我正在努力以算法的形式列举所有可能性。

我不希望有一个动态的编程答案，因为我很奇怪地设法弄清楚了这个答案（您会认为蛮力方法会更容易）。请使用伪代码，因为我更喜欢自己理解并自行编写。

Answer 1

它与 DP 减去记忆部分几乎相同。

LCS(s1, s2, i, j):
    if(i == -1 || j == -1)
        return 0
    if(s1[i] == s2[j])
        return 1 + LCS(s1, s2, i-1, j-1)
    return max(LCS(s1, s2, i-1, j), LCS(s1, s2, i, j-1))

这个想法是，如果我们有两个字符串 s1 和 s2，其中 s1 以 i 结束，s2 以 j 结束，那么 LCS 是：

• 如果任一字符串为空，则最长公共子序列为 0。
• 如果字符串 1 的最后一个字符（索引 i）与字符串 2 中的最后一个字符（索引 j）相同，则答案为 1 加上分别以 i-1 和 j-1 结尾的 s1 和 s2 的 LCS。因为很明显这两个指数对 LCS 有贡献，所以最好对它们进行计数。
• 如果最后一个字符不匹配，那么我们尝试删除其中一个字符。因此，我们尝试在 s1（以 i-1 结尾）和 s2（以 j 结尾）以及 s1（以 i 结尾）和 s2（以 j-1 结尾）之间找到 LCS，然后取两者的最大值。

时间复杂度显然是指数级的。

Answer 2

我喜欢@turingcomplete的答案，但这并不是真正的蛮力，因为它实际上并未列举所有候选解决方案。例如，如果字符串是“ ABCDE”和“ XBCDY”，则递归方法将不会测试“ ABC”和“ XBC”，因为对“ A”和“ X”的测试已经失败。不过，您是否想将其视为唯一的候选人也是一种观点。实际上，您可能会争辩说“ ABC”与“ ABCDY”也是有效的候选者，并且由于长度差异而立即失败。您可以在下面的代码中添加单独的LA和LB，以完全枚举这些候选对象。

for L = min(A.length, B.length) to 1
{
    for iA = 0 to A.length - L - 1
    {
        for iB = 0 to B.length - L - 1
        {
            for i = 0 to L - 1
            {
                if(A[iA] != B[iB])
                {
                    match failed;
                }
            }
            if match didn't fail, then
            A[iA..iA+L] and B[iB..iB+L] are a maximal common substring
        }
     }
}
no common substring