在string中查找最长的重复序列
我需要find一个string中最长的序列，必须重复三次或更多次。 所以，例如，如果我的string是：
fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld
那么我想要返回值“ helloworld ”。
我知道一些方法来完成这个，但我面临的问题是，实际的string是荒谬的大，所以我真的在寻找一种方法，可以及时做到这一点。
这个问题是最长的重复子串问题的一个变种，并且有一个O（n）时间algorithm来解决它，使用后缀树 。 这个想法（如维基百科所build议的）是构build一个后缀树（时间O（n）），树中的所有节点用后代数（使用DFS的时间O（n））进行注释，然后find树中最深的节点至less有三个后代（使用DFS的时间O（n））。 这整个algorithm需要时间O（n）。
也就是说，后缀树是非常难以构build的，所以在尝试这个实现之前，你可能想要find一个为你实现后缀树的Python库。 快速谷歌search出现这个库 ，但我不知道这是否是一个很好的实施。
希望这可以帮助！
使用defaultdict来计算从inputstring中每个位置开始的每个子string。 OP不清楚重叠匹配是否应该包括在内，这个powershell方法包括它们。
from collections import defaultdict def getsubs(loc, s): substr = s[loc:] i = -1 while(substr): yield substr substr = s[loc:i] i -= 1 def 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)
让我们从最后开始，计算频率，并在最频繁的元素出现3次或更多次时立即停止。
from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1)[::-1]: substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]>=3: seq=freqs.most_common(1)[0][0] break print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)
结果：
>>> sequence 'helloworld' of length 10 occurs 3 or more times
编辑：如果你有感觉，你正在处理随机input和公共子string应该是很小的长度，你最好开始（如果你需要的速度）与小的子串，并停止时，你不能find任何出现在最less3次：
from collections import Counter a='fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' times=3 for n in range(1,len(a)/times+1): substrings=[a[i:i+n] for i in range(len(a)-n+1)] freqs=Counter(substrings) if freqs.most_common(1)[0][1]<3: n-=1 break else: seq=freqs.most_common(1)[0][0] print "sequence '%s' of length %s occurs %s or more times"%(seq,n,times)
与上面相同的结果。
首先想到的第一个想法是逐渐寻找更大的正则expression式：
import re text = 'fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld' largest = '' i = 1 while 1: m = re.search("(" + ("\w" * i) + ").*\\1.*\\1", text) if not m: break largest = m.group(1) i += 1 print largest # helloworld
代码成功运行。 时间复杂度似乎至less是O（n ^ 2）。
如果反转input的string，然后将其input到正则expression式(.+)(?:.*\1){2}
它应该给你最长的string重复3次。 （反向捕获组1的答案）
编辑：
我不得不说这样取消。 这取决于第一场比赛。 除非目前为止对curr长度和最大长度进行testing，否则在迭代循环中，正则expression式不适用于此。
