문자열에서 가장 긴 반복 시퀀스 찾기

Question

시퀀스에서 세 번 이상 반복해야하는 경고가있는 문자열에서 가장 긴 시퀀스를 찾아야합니다. 따라서, 예를 들어, 내 문자열 인 경우 :

그때 나는 값 "helloworld를"반환하기를 원하는

fdwaw4helloworldvcdv1c3xcv3xcz1sda21f2sd1ahelloworldgafgfa4564534321fadghelloworld.

나는 이것을 수행하는 몇 가지 방법을 알고 있지만 내가 직면하고있는 문제는 실제 문자열이 어리석게 커지기 때문에시기 적절하게 그것을 할 수있는 방법을 찾고 있다는 것입니다.

Answer 1

이 문제는 longest repeated substring problem의 변형이며 suffix trees을 사용하는 해결을위한 O (n) 시간 알고리즘이 있습니다. Wikipedia에서 제안한 아이디어는 접미사 트리 (시간 O (n))를 만들고, 트리의 모든 노드에 하위 노드 수 (DFS를 사용하여 시간 O (n))를 주석으로 추가 한 다음 최소한 3 개의 하위 노드 (DFS를 사용하는 시간 O (n))가있는 트리의 가장 깊은 노드. 이 전체 알고리즘은 시간 O (n)을 필요로합니다.

말하자면, 접미어 트리는 작성하기가 어렵 기 때문에 악의를 띤 빌드를 구현하기 전에 접미어 트리를 구현하는 Python 라이브러리를 찾고 싶을 것입니다. 빠른 Google 검색은 this library으로 바뀌지 만, 좋은 구현인지 잘 모르겠습니다.

희망이 도움이됩니다.

Answer 2

마음에 온 첫 번째 생각은 점진적으로 더 큰 정규 표현식으로 검색한다 : 코드가 성공적으로 실행

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) 인 것으로 보입니다.

Answer 3

마지막부터 시작하여 가장 빈번한 요소가 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 

편집 : 당신은 당신이 작은 길이이어야 임의 입력과 일반 문자열을 취급하고있는 느낌이있는 경우, 당신은 더 나은 (당신이 필요로하는 경우 시작 속도는 작은 부분 문자열을 사용하고 적어도 세 번 나타나면 찾을 수 없을 때 중지하십시오.

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) 

위와 같은 결과입니다.

Answer 4

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) 

Answer 5

는 다음 (.+)(?:.*\1){2}
같은 정규식에 공급 그것은 당신에게 가장 긴 문자열을 제공해야 3 회 반복.(답에 대한 역 캡처 그룹 1)

편집 : 나는이 방법을 취소 말을
. 그것은 첫 번째 경기에 의존합니다. 지금까지 curr 길이 대 최대 길이를 테스트하지 않으면, 반복 루프에서 정규 표현식이 작동하지 않습니다.