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

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

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

那么我想值 “的HelloWorld” 将被返回。

我知道一些方法来完成这个，但我面临的问题是，实际的字符串是荒谬的大，所以我真的在寻找一种方法，可以及时做到这一点。

2012-06-18 Snesticle

我不知道是否有正则表达式解决这个问题。这个_不能是一个正则表达式，但是python可能有一个不规则的扩展，它可以做这样的事情。在一般情况下，这是LCS问题，可以使用动态编程来解决：http://en.wikipedia.org/wiki/Longest_common_subsequence_problem –

此问题是longest repeated substring problem的一个变体，并且存在O（n）时间算法来解决该问题，该算法使用suffix trees。这个想法（如维基百科所建议的）是构造后缀树（时间O（n）），用树的后代数（使用DFS的时间O（n））注解树中的所有节点，然后找到树中最深的节点至少有三个后代（使用DFS的时间O（n））。这个总体算法需要时间O（n）。

也就是说，后缀树非常难以构建，因此您可能希望在尝试执行此实现之前找到为您实施后缀树的Python库。快速谷歌搜索变成了this library，但我不确定这是否是一个好的实现。

希望这会有所帮助！

来源

2012-06-18 20:17:32 templatetypedef

“臭名昭着的难以构建” - 说什么？ –

@ KonradRudolph-我不知道任何“简单”算法在线性时间构造后缀树。我所知道的两种算法（Ukkonen算法和DC3算法）非常复杂，并且没有明显的正确性证明。这就是说，如果我误解了这一点，我很乐意纠正！ – templatetypedef

我同意证明不是微不足道的。但是，对于Ukkonen算法存在伪代码，这些代码很容易适应。此外，尽管线性时间算法很难找到，但还存在平凡派生的非线性构造算法，但在实践中表现得相当好。 –

浮现在脑海的第一个念头是与逐渐变大的正则表达式搜索：

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-18 21:11:59

。答案应该是'ana 2 times' –

让我们从最后开始，计数频率，并在最频繁元素出现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-18 21:31:20

也就是说，从'M = len（a）/ N'（其中N是reps的最小数目）开始构建每个子集M个项目，并且计数这些reps每个。如果没有子字符串的出现次数> = N，则从M中减去1并再次尝试。是？ – PaulMcG

@PaulMcGuire –

我试图在相反的方向（小到大）类似的东西。任何想法你的方法的时间复杂性是什么？ –

使用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-18 21:36:26 PaulMcG

我真的很喜欢这个解决方案，但不幸的是我的琴弦通常太大了。然而，我敢打赌，你的答案对于通过谷歌登陆谷歌的许多人来说非常有用，因为它确实解决了我给出的最好例子。 – Snesticle

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

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

来源

2012-06-18 22:00:55 sln

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

回答

相关问题