Znajdź najdłuższą powtarzalną sekwencję w ciągu znaków

Question

Potrzebuję znaleźć najdłuższą sekwencję w ciągu znaków z zastrzeżeniem, że sekwencja musi zostać powtórzona trzy lub więcej razy. Tak więc, na przykład, jeśli mój ciąg jest:

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld

następnie chciałbym wartość "helloworld" być zwrócony.

Wiem o kilku sposobach osiągnięcia tego, ale problemem, z którym się borykam, jest fakt, że rzeczywista struna jest absurdalnie duża, więc naprawdę szukam metody, która może to zrobić we właściwym czasie.

Answer 1

Ten problem jest wariantem longest repeated substring problem i istnieje algorytm O (n) -time do jego rozwiązania, który używa suffix trees. Pomysł (zgodnie z sugestią Wikipedii) polega na stworzeniu drzewa sufiksów (czas O (n)), dodaniu adnotacji do wszystkich węzłów drzewa z liczbą potomków (czas O (n) przy użyciu DFS), a następnie znalezieniu najgłębszy węzeł drzewa z co najmniej trzema potomkami (czas O (n) przy użyciu DFS). Ten ogólny algorytm wymaga czasu O (n).

Powiedziane, przyrostki drzew są bardzo trudne do skonstruowania, więc prawdopodobnie będziesz chciał znaleźć bibliotekę Pythona, która zaimplementuje drzewa sufiksów przed wykonaniem tej implementacji. Szybka wyszukiwarka Google pojawia się this library, ale nie jestem pewien, czy jest to dobra implementacja.

Mam nadzieję, że to pomoże!

Answer 2

Pierwszy pomysł, który przyszedł mi do głowy jest poszukiwanie coraz większych z wyrażeń regularnych:

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 

Kod przebiegały pomyślnie. Złożoność czasu wydaje się wynosić co najmniej O (n^2).

Answer 3

Zacznijmy od końca, policz częstotliwość i zatrzymaj się, gdy tylko najczęstszy element pojawi się 3 lub więcej razy.

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) 

Wynik:

>>> sequence 'helloworld' of length 10 occurs 3 or more times 

Edit: jeśli masz wrażenie, że masz do czynienia z losowym wejście i wspólny podciąg powinien mieć małą długością, lepiej zacząć (jeśli trzeba prędkość) z małych podciągów i zatrzymać, gdy nie można znaleźć żadnego, które pojawiają się co najmniej 3 czas:

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) 

Taki sam wynik jak wyżej.

Answer 4

Użyj defaultdict, aby dopasować każdy ciąg rozpoczynający się z każdą pozycją w łańcuchu wejściowym. OP nie było jasne, czy nakładające się mecze powinny lub nie powinny zostać uwzględnione, ta metoda brutalnej siły obejmuje je.

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

drukuje:

('helloworld', 3) 

Answer 5

Jeśli odwrócić ciąg wejściowy, a następnie karmić je regex jak (.+)(?:.*\1){2}
powinno to daje najdłuższy łańcuch powtórzony 3 razy.(Wsteczny grupa przechwytywania 1 dla odpowiedzi)

Edit:
muszę powiedzieć anulować ten sposób. To zależy od pierwszego meczu. O ile nie przetestowano go pod względem długości curra względem maksymalnej długości, w pętli iteracyjnej regex nie będzie działał.