40

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

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

那么我希望返回值“ helloworld ”。

我知道实现这一点的几种方法，但我面临的问题是实际的字符串大得离谱，所以我真的在寻找一种可以及时完成的​​方法。

4

6 回答 6

33

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

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

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

构建后缀数组有几种简单的算法（Manber-Myers 算法在 O(n log n) 时间内运行，并且编码起来并不难），而 Kasai 的算法在 O(n) 时间内构建 LCP 数组并且相当直接编码。

希望这可以帮助！

于 2012-06-18T20:17:32.607 回答
12

使用 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)
于 2012-06-18T21:36:26.187 回答
4

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

结果与上面相同。

于 2012-06-18T21:31:20.023 回答
1

想到的第一个想法是使用逐渐变大的正则表达式进行搜索：

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

代码运行成功。时间复杂度似乎至少为 O(n^2)。

于 2012-06-18T21:11:59.793 回答
0

如果您反转输入字符串，则将其提供给正则表达式，例如(.+)(?:.*\1){2}
它应该给您最长的字符串重复 3 次。（反向捕获组 1 为答案）

编辑：
我不得不说取消这种方式。这取决于第一场比赛。除非到目前为止针对当前长度与最大长度进行了测试，否则在迭代循环中，正则表达式不适用于此。

于 2012-06-18T22:00:55.283 回答
-1 
from collections import Counter

def Longest(string):

    b = []
    le = []

    for i in set(string):

        for j in range(Counter(string)[i]+1): 
            b.append(i* (j+1))

    for i in b:
        if i in string:
            le.append(i)


    return ([s for s in le if len(s)==len(max( le , key = len))])
于 2019-03-12T16:07:34.267 回答