来自两个以上字符串的最长公共子字符串 - 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

希望这可以帮助,

杰森.

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)

集合（可能）被实现为哈希映射，这使得这有点低效。如果您 (1) 将 set 数据类型实现为 trie 并且 (2) 仅将后缀存储在 trie 中，然后强制每个节点成为端点（这相当于添加所有子字符串），那么理论上我猜这个婴儿的记忆效率很高，特别是因为尝试的交叉点非常容易。

然而，这是短暂的，过早的优化是大量浪费时间的根源。