在字符串中查找重复

Question

两天来，我一直在研究这个问题，但没有发现任何东西，所以我决定写我自己的字符串重复检测器。基本上是功能

def findRepetitions (string):

将接收字符串并搜索任何重复项；返回简化为最简单形式的字符串列表。在

作为一个样本，应该是：

^{pr2}$

在第三个例子中，函数返回[“l”，“l”]而不是[“ll”]，因为我只想搜索相邻字符中的重复。在

我知道这可能很难，但我已经仔细考虑了很久，没有找到任何明智的解决办法。在

Answer 1

这是一个众所周知的问题：

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

您可以有效地解决此问题，但需要构建一个trie：

http://en.wikipedia.org/wiki/Radix_tree

wiki页面显示了用于查找和添加节点的伪代码和示例，这些是您所需的唯一函数。 在trie中从每个字符开始插入字符串，例如，对于字符串yi dong插入abcd，bcd，cd，d。 trie的这个特定实例称为“后缀树”：

http://en.wikipedia.org/wiki/Suffix_tree

每次遍历已经建立的路径时，实际上都会发现字符串中存在重复。 现在，您可以在一个单独的数据结构中列出所有重复，并提取最长的一个（如果需要）。在

Answer 2

你的例子不一致。例如，olo不重复，就像Hello, Molly中的l，`trololololo中的l；实例之间有一个l。trololololo中的顺序重复是lolo，lo，olol，和{}。你在问一个“贪婪”算法吗？所以，给定trololololo，它会返回olol？在

无论如何，这里有一些代码。在

from collections import Counter

def find_repetition(p):
    """ Returns a lookup dictionary for repetitions. """ 
    lookup = Counter()
    while len(p) != 0:
        for i in xrange(len(p)):
            lookup[p[0:i]] += 1
        p = p[1:]
    return lookup

def repeats(p):
    a = find_repetition(p)
    rs = [i for i in a if a[i] > 1][1:]
    return [r for r in rs if r*2 in p]

如果你想让它像我描述的那样“贪婪”，你必须添加另一个函数，当它找到匹配项时，它会从repeats和chomps中获取结果。在

目前，结果如下：

^{pr2}$

警告

find_repetition不是很快，因为它基本上生成字符串的所有长度组合并将它们放入Counter对象。在