Python中最长的公共子序列

Question

我试图找到两个字符串之间最长的公共子序列。

我观看了这个教学标签https://www.youtube.com/watch?v=NnD96abizww

并写道：

# Longest Common Subsequence

def lcs(s1, s2):
    matrix = [ [0 for x in range(len(s2))] for x in range(len(s1)) ]
    cs = ""
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i]==s2[j]:
                if i==0 or j==0:
                    matrix[i][j] = 1
                    cs += s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + 1
                    cs += s1[i]
            else:
                if i==0 or j==0:
                    matrix[i][j] = 0
                else:
                    matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])

    return matrix[len(s1)-1][len(s2)-1], cs


print(lcs("abcdaf", "acbcf"))  



I get (3, 'abccaf')

这显然是错误的，应该是4 abcf。

不知道哪一步出错了。一个普遍的问题是程序员通常花多长时间才能“解决”这类问题？

Answer 1

对于那些寻找内置解决方案的人：

from difflib import SequenceMatcher

str_a = "xBCDxFGxxxKLMx"
str_b = "aBCDeFGhijKLMn"
s = SequenceMatcher(None, str_a, str_b)

lcs = ''.join([str_a[block.a:(block.a + block.size)] for block in s.get_matching_blocks()])
# lcs = 'BCDFGKLM'

Answer 2

您的代码有2个主要问题，这些问题会导致算法输出错误的答案。

if i == 0 or j == 0 在第16行

紧随视频之后，该行仅显示，这是没有意义的s1[1] != s2[j]，尽管“ ab”和“ a”的最长公共子序列的长度为1，尽管您matrix[0][1] = 0为该示例设置了算法。因此，您需要删除此if语句。虽然你在它，你必须要考虑什么max(matrix[i-1][j], matrix[i][j-1])对做i == 0或j == 0。现在有两种不同的方法：

1. 明确的一个：

   max(matrix[i-1][j] if i != 0 else 0, 
       matrix[i][j-1] if j != 0 else 0)
   

2. 隐式的一个：

   max(matrix[i-1][j], matrix[i][j-1])
   

   之所以可行，是因为在Python中，负索引用于获取列表的最后一项，在这种情况下，这些项为0。

cs += s1[i] 在11/14行

例如，如果您发现“ a”和“ abcd”的最长公共子序列是“ a”，则您的算法会将“ a”和“ abcda”的最长公共子序列设置为“ aa”，这没有意义。我正在努力解释为什么它不能那样工作，所以我建议您看一些示例，也许使用http://pythontutor.com/visualize.html

解

为了解决这两个问题，您可以使用矩阵存储发现较小问题的最长公共子序列。您最终得到以下结果：

def lcs(s1, s2):
    matrix = [["" for x in range(len(s2))] for x in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = s1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + s1[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]

    return len(cs), cs

print(lcs("abcdaf", "acbcf"))  

此特定实现仅返回一个可能的结果。您可以尝试实现一种算法，该算法给出所有最长的公共序列作为练习。也许看看????建议的Wikipedia页面。????

“了解”您的代码为何不起作用需要多长时间？

显然没有明确的答案。它总是有助于思考示例，在算法的情况下，Wikipedia通常具有良好的伪代码，您可以将其作为实现的基础。我想说，当您熟悉算法中涉及的概念和数据结构时，您应该可以在一天内实现它（但我绝对不是专家）。通常，根据代码的大小，在代码中搜索逻辑错误可能需要花费几天的时间。为了实践这种结构化，算法和数学思维，我强烈建议您使用projecteuler.net。