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

Question

我需要找到字符串中最长的序列，并警告序列必须重复三次或更多次。例如，如果我的字符串是：

fdwaw4helloworld vcdv1c3xcv3xcz1sda21f2sd1ahelloworld gafgfa4564534321fadghelloworld

然后我希望返回值“helloworld”。

我知道有几种方法可以做到这一点，但我面临的问题是，实际的字符串太大了，所以我真的在寻找一种能够及时做到这一点的方法。

Answer 1

让我们从头开始，统计频率，当最频繁的元素出现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) 

与上述结果相同。

Answer 2

使用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)

Answer 3

这个问题是最长重复子串问题的变体，有一个使用后缀树的O（n）时间算法来解决它。这个想法（正如维基百科所建议的）是构建一个后缀树（时间O（n）），用子代的数量（时间O（n）使用DFS）注释树中的所有节点，然后用at找到树中最深的节点至少三个后代（使用DFS的时间O（n））。这种总体算法需要时间O（n）。

也就是说，众所周知，后缀树很难构建，所以在尝试这个实现之前，您可能希望找到一个为您实现后缀树的Python库。一个快速的谷歌搜索会出现这个库，尽管我不确定这是否是一个好的实现。

另一种选择是将后缀数组与LCP数组结合使用。您可以迭代LCP数组中的相邻元素对，取每对的最小值，并以这种方式存储您找到的最大值。这将对应于重复至少三次的最长字符串的长度，然后您可以从那里读取字符串本身。

有几种简单的算法可用于构建后缀数组（Manber-Myers算法在时间O（n logn）内运行，编码也不太困难），Kasai的算法在时间O（n）内构建LCP数组，编码起来相当简单。

希望这有帮助！