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

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

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

세계 4

그러면 "helloworld"값을 반환하고 싶습니다.

나는 이것을 성취 할 수있는 몇 가지 방법을 안다. 그러나 내가 직면하고있는 문제는 실제 문자열이 터무니없이 크다. 그래서 나는 적시에 그것을 할 수있는 방법을 찾고있다.

해결법

1. ==============================

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

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

   즉, 접미어 트리는 작성하기가 매우 어렵 기 때문에이 구현을 시도하기 전에 접미어 트리를 구현하는 Python 라이브러리를 찾고 싶을 것입니다. 빠른 구현 여부는 확실하지 않지만 빠른 Google 검색을 통해이 라이브러리가 나타납니다.

   희망이 도움이!

2. ==============================

   2.defaultdict를 사용하여 입력 문자열의 각 위치로 시작하는 각 부분 문자열을 집계하십시오. OP는 겹쳐진 성냥이 포함되어야하는지 포함되어서는 안되는지 명확하지 않았지만,이 무차별 방식에는 그것도 포함됩니다.

   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)
   

3. ==============================

   3.끝에서부터 시작하여 가장 빈번한 요소가 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
   

   편집 : 무작위 입력을 처리하고 일반 하위 문자열의 길이가 짧아야한다는 느낌이 들게되면 작은 하위 문자열로 시작 (속도가 필요한 경우)하고 시작 부분을 찾을 수 없을 때 중지하십시오 최소 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) 
   

   위와 같은 결과입니다.

4. ==============================

   4.입력 문자열을 뒤집어서 (. +) (? :. * \ 1) {2}와 같은 정규식에 입력하면, 그것은 당신에게 3 번 반복되는 가장 긴 문자열을 제공해야합니다. (답변에 대해 역 캡처 그룹 1)

   입력 문자열을 뒤집어서 (. +) (? :. * \ 1) {2}와 같은 정규식에 입력하면, 그것은 당신에게 3 번 반복되는 가장 긴 문자열을 제공해야합니다. (답변에 대해 역 캡처 그룹 1)

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

5. ==============================

   5.마음에 떠오른 첫 번째 아이디어는 점점 커지는 정규 표현식을 사용하여 검색하는 것입니다.

   마음에 떠오른 첫 번째 아이디어는 점점 커지는 정규 표현식을 사용하여 검색하는 것입니다.

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

from https://stackoverflow.com/questions/11090289/find-longest-repetitive-sequence-in-a-string by cc-by-sa and MIT license