algorithm - 最长公共子序列 (LCS) 蛮力算法

Question

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

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

Answer 1

我喜欢@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

Answer 2

这与 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）之间的 LCS 以及 s1（结束于 i）和 s2（结束于 j-1）之间的 LCS，然后取两者的最大值。

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

Answer 3

这是一个 Java 方法，它在 ArrayList 中存储/列出给定字符串的所有子序列。

• 查找给定 2 个字符串的所有子序列
  

• 找出他们之间的共同点
  

• 其中最长的一个就是答案
  

• 我们已经知道每个字符可能
  1) 出现
  或
  2) 不出现在
  任何子序列中。
  

• 因此，我们保持 ArrayList 中的所有字符串不变（上面的 case-2）。
  

• 此外，我们添加（到 ArrayList）字符串，这些
  字符串是 ArrayList 中已经存在的字符串与字符串的下一个字符
  （上面的 case-1）连接的结果。
  

• 这涵盖（解决）了我们问题的上述两种情况。
  

• 我们这样做直到字符串中的所有字母。
  

ArrayList<String> subseq(String s)
    {
        ArrayList<String> h = new ArrayList<String>();
        h.add("");
        int n = s.length();
        int l;
        for(int i=0;i<n;i++)
        {
            l = h.size();
            for(int j=0;j<l;j++)
                h.add( h.get(j) + s.charAt(i));
        }
        return h;
    }