使用动态规划的最长公共子串

Question

我编写了一个简短的python脚本，它试图解决使用动态编程技术寻找最长的公共子字符串的问题。它应该是泛化的，这样我就可以插入任意数量的字符串，并找到最长的公共子字符串。

def longest_common_substring(*strings):
    table = defaultdict(int)
    for pos in product(*(range(len(s)) for s in strings)):
        same = len(set(s[i] for s, i in zip(strings, pos))) is 1
        table[pos] = table[tuple(map(lambda n: n - 1, pos))] + 1 if same else 0
    return max(table.items(), key=operator.itemgetter(1))

对于少量短字符串来说，这是很好的，但是空间和时间复杂度肯定会随着较长的字符串而变大。

我从维基百科获得了这一点，而且由于这种方法对于多个更长的字符串来说显然很糟糕(或者我的实现是糟糕的！？)，我想知道我能做些什么来改进它？维基百科也有一个通用的后缀树..。我对他们一点也不熟悉，那会是一个更好的方法吗？

而且，如果这是我的实现，我很想知道哪里出了问题，在空间复杂性方面我可以做得更好。

Answer 1

很抱歉，我没有仔细检查您的代码，无法发表评论，但考虑到前面提到的问题和您正在使用Py3的事实，我可能会用itertools.accumulate来解决它，例如：

>>> import itertools as it
>>> import operator as op
>>> ss = ["thisishello", "dfdsishdllo", "ashsisdsdsf"]
>>> i, l = max(enumerate(it.accumulate(it.chain([0], zip(*ss)),
...                      lambda x, y: (x+1)*(len(set(y)) == 1))), key=op.itemgetter(1))
>>> i, l, ss[0][i-l:i]
(6, 3, 'sis')

对于任意数量的字符串，应该可以很好地工作，因为它使用生成器，并且不创建任何中间数据结构。

它确实使用了一个事实，即False等同于len(set(y)) == 1的0，但如果这让人不舒服，您可以简单地用1 if len(set(y)) == 1 else 0替换。

注意:我仍然希望itertools.accumulate有一个和functools.reduce一样的初始值参数，这样就避免了chain将初始值转换为可迭代的需要。