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

Question

我需要在字符串中找到最长的序列,但需要注意序列必须重复三次或更多次.所以,例如,如果我的字符串是:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

然后我想要返回值" helloworld ".

我知道有几种方法可以实现这个目标,但我面临的问题是实际的字符串非常大,所以我真的在寻找一种可以及时完成的​​方法.

Answer 1

这个问题是最长的重复子字符串问题的变体,并且有一个O(n)-time算法用于解决它使用后缀树.这个想法(由维基百科建议)是构造一个后缀树(时间O(n)),使用后代数量注释树中的所有节点(使用DFS的时间O(n)),然后找到树中最深的节点,至少有三个后代(使用DFS的时间为O(n)).该整体算法花费时间O(n).

也就是说,后缀树很难构建,所以你可能想要在尝试这个实现之前找到一个为你实现后缀树的Python库.一个快速的谷歌搜索出现了这个库,但我不确定这是否是一个很好的实现.

希望这可以帮助!

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)