两个以上字符串中最长的公共子字符串-Python

Question

我正在寻找一个Python库，用于从 一组字符串中 找到最长的公共子 字符串 。有两种方法可以解决此问题：

• 使用后缀树
• 使用动态编程。

实施的方法并不重要。重要的是，它可以用于 一组字符串 （不仅是两个字符串）。

Answer 1

这些成对的函数将在任意字符串数组中找到最长的公共字符串：

def long_substr(data):
    substr = ''
    if len(data) > 1 and len(data[0]) > 0:
        for i in range(len(data[0])):
            for j in range(len(data[0])-i+1):
                if j > len(substr) and is_substr(data[0][i:i+j], data):
                    substr = data[0][i:i+j]
    return substr

def is_substr(find, data):
    if len(data) < 1 and len(find) < 1:
        return False
    for i in range(len(data)):
        if find not in data[i]:
            return False
    return True


print long_substr(['Oh, hello, my friend.',
                   'I prefer Jelly Belly beans.',
                   'When hell freezes over!'])

毫无疑问，该算法可以得到改进，而且我对Python的接触也很少，因此也许它在语法上也可能更有效，但是它应该可以完成工作。

编辑： 内联第二个is_substr函数，如JF Sebastian所示。用法保持不变。注意：算法无变化。

def long_substr(data):
    substr = ''
    if len(data) > 1 and len(data[0]) > 0:
        for i in range(len(data[0])):
            for j in range(len(data[0])-i+1):
                if j > len(substr) and all(data[0][i:i+j] in x for x in data):
                    substr = data[0][i:i+j]
    return substr

希望这可以帮助，

杰森