来自两个以上string的最长公共子string – Python

我正在寻找一个Python库来查找一组string中最长的公共子string 。 有两种方法可以解决这个问题：

• 使用后缀树
• 使用dynamic编程。

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

Answer 1

这些成对的函数将在任意string数组中find最长的公共string：

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!']) 

毫无疑问，这个algorithm可以被改进，而且我还没有对Python有太多的接触，所以也许它在语法上也可能更高效，但是它应该能够完成这项工作。

编辑：插入第二个is_substr函数由JF Sebastian演示。 用法保持不变。 注意：algorithm没有改变。

 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

我更喜欢这个is_substr ，因为我觉得它更具可读性和直观性：

 def is_substr(find, data): """ inputs a substring to find, returns True only if found for each data in data list """ if len(find) < 1 or len(data) < 1: return False # expected input DNE is_found = True # and-ing to False anywhere in data will return False for i in data: print "Looking for substring %s in %s..." % (find, i) is_found = is_found and find in i return is_found 

Answer 3

 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 4

您可以使用SuffixTree模块，该模块是基于通用后缀树的ANSI C实现的包装器。 该模块很容易处理….

看看： 在这里

Answer 5

 # this does not increase asymptotical complexity # but can still waste more time than it saves. TODO: profile def shortest_of(strings): return min(strings, key=len) def long_substr(strings): substr = "" if not strings: return substr reference = shortest_of(strings) #strings[0] length = len(reference) #find a suitable slice i:j for i in xrange(length): #only consider strings long at least len(substr) + 1 for j in xrange(i + len(substr) + 1, length + 1): candidate = reference[i:j] # ↓ is the slice recalculated every time? if all(candidate in text for text in strings): substr = candidate return substr 

免责声明这对jjjacques的答案几乎没有增加。 但是，希望这应该是更可读和更快，它不适合发表评论，所以我发布这个答案。 说实话，我并不满意shortest_of 。

Answer 6

这可以做得更短：

 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）实现一个数据types作为一个trie和（2）只是将后缀存储在trie中，然后强制每个节点作为一个端点（这将等于添加所有子string），那么在理论上，我猜测这个宝贝的记忆效率很高，特别是因为尝试的交叉是非常容易的。

尽pipe如此，这是短暂的，不成熟的优化是大量浪费时间的根源。

Answer 7

如果有人正在寻找一个通用版本，也可以采取一系列任意对象的列表：

 def get_longest_common_subseq(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_subseq_of_any(data[0][i:i+j], data): substr = data[0][i:i+j] return substr def is_subseq_of_any(find, data): if len(data) < 1 and len(find) < 1: return False for i in range(len(data)): if not is_subseq(find, data[i]): return False return True # Will also return True if possible_subseq == seq. def is_subseq(possible_subseq, seq): if len(possible_subseq) > len(seq): return False def get_length_n_slices(n): for i in xrange(len(seq) + 1 - n): yield seq[i:i+n] for slyce in get_length_n_slices(len(possible_subseq)): if slyce == possible_subseq: return True return False print get_longest_common_subseq([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]]) print get_longest_common_subseq(['Oh, hello, my friend.', 'I prefer Jelly Belly beans.', 'When hell freezes over!'])