Python에서 문자열의 가장 긴 반복 시퀀스를 찾는 방법

Python에서 문자열 안에 두 번 이상 등장하는 가장 긴 부분 문자열(반복 시퀀스)을 찾으려면 collections.defaultdict를 활용하여 입력 문자열의 각 위치에서 시작하는 모든 부분 문자열의 등장 횟수를 집계하는 방식을 사용할 수 있습니다.

여기서 getsubs 함수는 제너레이터(generator)로 구현되어 있으며, 호출될 때마다 지정된 위치에서 시작하는 부분 문자열을 하나씩, 점점 짧은 길이로 생성하여 반환합니다.

구현 예제

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):
    occ = defaultdict(int)
    # 모든 부분 문자열의 등장 횟수를 집계
    for i in range(len(r)):
        for sub in getsubs(i,r):
            occ[sub] += 1
    # 두 번 미만으로 등장한 부분 문자열은 제외
    filtered = [k for k,v in occ.items() if v >= 2]
    if filtered:
        maxkey = max(filtered, key=len) # 가장 긴 문자열 탐색
        return maxkey
    else:
        raise ValueError("no repetitions of any substring of '%s' with 2 or more occurrences" % (r))
longestRepetitiveSubstring("hellopeople18654randomtexthellopeoplefromallaroundthe world")

동작 원리

1. 문자열의 모든 시작 위치에 대해 가능한 모든 부분 문자열을 생성합니다.
2. defaultdict(int)를 사용해 각 부분 문자열이 몇 번 등장했는지 카운트합니다.
3. 두 번 이상 등장한 부분 문자열만 필터링하여 남깁니다.
4. 필터링된 후보 중 가장 긴 것을 max(filtered, key=len)으로 선택해 반환합니다.

만약 반복되는 부분 문자열이 하나도 존재하지 않는다면, 해당 사실을 알리는 ValueError가 발생하도록 처리되어 있습니다.

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다:

'hellopeople'

입력 문자열에서 "hellopeople"이라는 부분 문자열이 정확히 두 번 반복되어 나타나며, 그중 가장 길기 때문에 최종 결과로 반환됩니다.

참고 사항

이 방법은 모든 부분 문자열을 일일이 생성하고 집계하기 때문에 구현이 직관적이지만, 문자열 길이가 n일 때 시간 복잡도가 대략 O(n³) 수준으로 증가할 수 있습니다. 따라서 매우 긴 문자열을 다룰 경우에는 서픽스 배열(suffix array)이나 서픽스 트리(suffix tree)를 이용한 알고리즘을 고려하는 것이 좋습니다.