查找字符串中最长的重复序列
我需要在字符串中找到最长的序列，但必须重复三次或三次以上。因此，例如，如果我的字符串是：
fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld
然后，我希望返回值"helloworld“。
我知道有几种方法可以实现这一点，但是我面临的问题是，实际的字符串非常大，所以我真的在寻找一种能够及时完成的方法。
回答 6
Stack Overflow用户
发布于 2012-06-18 20:17:32
这个问题是最长重复子串问题的一个变体，有一个使用后缀树求解它的O(n)-time算法。这个想法(如Wikipedia所建议的)是构建一个后缀树(time O(n))，用后代数(时间O(n) )注释树中的所有节点，然后使用DFS查找树中至少有三个后代的最深节点(时间O(n) )。整个算法需要时间O(n)。
也就是说，众所周知，后缀树很难构建，所以在尝试这个实现之前，您可能希望找到一个为您实现后缀树的Python库。谷歌快速搜索这个图书馆，但我不确定这是否是一个很好的实现。
另一种选择是将后缀数组与LCP阵列结合使用。您可以在LCP数组中的相邻元素对上迭代，取每对的最小值，并以这种方式存储最大的数目。这将与至少重复三次的最长字符串的长度相对应，然后您可以从那里读取字符串本身。
构建后缀数组有几种简单的算法(Manber算法在时间上运行O(n log )，并且不太难编码)，Kasai的算法在时间O(n)中构建LCP数组，并且非常简单。
希望这能有所帮助！
Stack Overflow用户
发布于 2012-06-18 21:36:26
使用defaultdict对每个子字符串进行计数，从输入字符串中的每个位置开始。OP不清楚是否应该包括重叠匹配，这种蛮力方法包括它们。
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)Stack Overflow用户
发布于 2012-06-18 21:31:20
让我们从结尾开始，计数频率，并在最频繁的元素出现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编辑：--如果您觉得自己在处理随机输入，而公共子字符串的长度应该很小，则最好用小子字符串启动(如果需要速度)，如果找不到至少3次出现的子字符串，则停止：
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) 与上面的结果相同。
https://stackoverflow.com/questions/11090289
复制相似问题
腾讯云开发者
