查找字符串中最长的重复序列

Question

我需要找到一个字符串中最长的序列，但要注意的是，该序列必须重复三次或更多次。因此，例如，如果我的字符串是：

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

那么我想返回值“ helloworld ”。

我知道完成此操作的几种方法，但是我面临的问题是实际的字符串非常大，因此我确实在寻找一种可以及时实现的方法。

Answer 1

这个问题是最长重复子串问题的一个变体，并且存在一个使用后缀树的O（n）时间算法来解决。这个想法（如Wikipedia所建议）是构造后缀树（时间O（n）），用后代数注释树中的所有节点（使用DFS的时间O（n）），然后找到树中具有至少三个后代的最深节点（使用DFS的时间O（n））。该总体算法花费时间O（n）。也就是说，众所周知，后缀树很难构建，因此您可能想要在尝试此实现之前，找到一个为您实现后缀树的Python库。快速的Google搜索打开了这个库，尽管我不确定这是否是一个很好的实现。希望这可以帮助！

Answer 2

使用defaultdict对从输入字符串中每个位置开始的每个子字符串进行计数。OP尚不清楚是否应该包含重叠的匹配项，这种蛮力方法包括它们。from collections import defaultdictdef getsubs(loc, s):    substr = s[loc:]    i = -1    while(substr):        yield substr        substr = s[loc:i]        i -= 1def longestRepetitiveSubstring(r, minocc=3):    occ = defaultdict(int)    # tally all occurrences of all substrings    for i in range(len(r)):        for sub in getsubs(i,r):            occ[sub] += 1    # filter out all substrings with fewer than minocc occurrences    occ_minocc = [k for k,v in occ.items() if v >= minocc]    if occ_minocc:        maxkey =  max(occ_minocc, key=len)        return maxkey, occ[maxkey]    else:        raise ValueError("no repetitions of any substring of '%s' with %d or more occurrences" % (r,minocc))印刷品：('helloworld', 3)

Answer 3

让我们从头开始，计算频率，并在出现最频繁的元素3次或更多次后立即停止。from collections import Countera='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld'times=3for n in range(1,len(a)/times+1)[::-1]:&nbsp; &nbsp; substrings=[a[i:i+n] for i in range(len(a)-n+1)]&nbsp; &nbsp; freqs=Counter(substrings)&nbsp; &nbsp; if freqs.most_common(1)[0][1]>=3:&nbsp; &nbsp; &nbsp; &nbsp; seq=freqs.most_common(1)[0][0]&nbsp; &nbsp; &nbsp; &nbsp; breakprint "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)结果：>>> sequence 'helloworld' of length 10 occurs 3 or more times编辑：如果您感觉自己正在处理随机输入，并且公共子字符串的长度应该很小，那么最好以小子字符串开始（如果需要速度），而当找不到任何出现在该子字符串时停止至少3次：from collections import Countera='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld'times=3for n in range(1,len(a)/times+1):&nbsp; &nbsp; substrings=[a[i:i+n] for i in range(len(a)-n+1)]&nbsp; &nbsp; freqs=Counter(substrings)&nbsp; &nbsp; if freqs.most_common(1)[0][1]<3:&nbsp; &nbsp; &nbsp; &nbsp; n-=1&nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; seq=freqs.most_common(1)[0][0]print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)&nbsp;与上述相同的结果。