多个字符串的最长公共子串

Question

我在找一个Python库，可以用来找出一组字符串中最长的公共子串。解决这个问题有两种方法：

• 使用后缀树
• 使用动态规划

具体用哪种方法并不重要，重要的是这个库能够处理一组字符串，而不仅仅是两个字符串。

Answer 1

def common_prefix(strings):
    """ Find the longest string that is a prefix of all the strings.
    """
    if not strings:
        return ''
    prefix = strings[0]
    for s in strings:
        if len(s) < len(prefix):
            prefix = prefix[:len(s)]
        if not prefix:
            return ''
        for i in range(len(prefix)):
            if prefix[i] != s[i]:
                prefix = prefix[:i]
                break
    return prefix

来自 http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py

Answer 2

这可以做得更简洁：

def long_substr(data):
  substrs = lambda x: {x[i:i+j] for i in range(len(x)) for j in range(len(x) - i + 1)}
  s = substrs(data[0])
  for val in data[1:]:
    s.intersection_update(substrs(val))
  return max(s, key=len)

集合（set）可能是用哈希表实现的，这样会有点低效。如果你（1）把集合的数据类型实现为字典树（trie），并且（2）只在字典树中存储后缀，然后强制每个节点都是一个结束点（这相当于添加所有子字符串），那么理论上我觉得这样会非常节省内存，特别是因为字典树的交集操作非常简单。

不过，这种方法虽然简短，但过早的优化往往会浪费很多时间。

Answer 3

这两个配对的函数可以在任何字符串数组中找到最长的公共字符串：

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的了解也不多，所以可能在语法上也可以更高效，但它应该能完成任务。

编辑：根据J.F. Sebastian的建议，把第二个is_substr函数合并进来了。使用方法还是一样的。注意：算法没有改变。

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

希望这对你有帮助，

Jason。