Python中的LCS只是长度上的交集函数吗？

Question

我试图优化 returns 两个字符串之间最长公共子串的长度的代码，并意识到插入函数 returns 几乎相同。我说得对吗？

a = input()
b = input()
print (len(set(a).intersection(b)))

Answer 1

不，因为您的单词交集会将单个字母分解为列表元素。例如，

a = 'abcd'
b = 'dcba'

变成

a = ['a', 'b', 'c', 'd']
b = ['d', 'c', 'b', 'a']

交集的长度将为 4，但这对您的情况不正确，因为 'abcd' 和 'dcba' 没有长度超过 1 的公共子串。

此外，对单词使用 set 会删除单词中的所有重复字母，这也会使搜索公共子字符串变得混乱。

您需要做的是将这两个词拆分成列出所有可能的子字符串，就像 post 中所做的一样。然后你可以对这些列表进行交集并取最大长度的元素。