查找字符串中最長的重複序列

我需要找到字符串中最長的序列，並注意序列必須重複三次或更多次。因此，舉例來說，如果我的字符串是：查找字符串中最長的重複序列

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

查找字符串中最長的重複序列

回答

相關問題