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

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

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

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

这些成对的函数将在任意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 

希望这可以帮助,

杰森。

我更喜欢这个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 
 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

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

看看: 在这里

 # 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

这可以做得更短:

 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如此,这是短暂的,不成熟的优化是大量浪费时间的根源。

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

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