4.2 Suffix Arrays(접미사 배열)

Suffix Arrays

Suffix arrays are a data structure that allows us to quickly find all the suffixes of a string in lexicographical order. This is useful for many problems, such as finding the longest common substring between two strings, or finding the number of distinct substrings of a string.

접미사 배열은 사전적 순서로 문자열의 모든 접미사를 빠르게 찾을 수 있는 데이터 구조입니다. 이는 두 문자열 사이의 가장 긴 공통 부분 문자열을 찾거나 문자열의 고유한 부분 문자열의 수를 찾는 등의 여러 문제에 유용합니다.

 

접미사 배열(Suffix Arrays)는 문자열 검색 알고리즘에서 효율적인 검색을 위해 사용되는 자료구조입니다. 주어진 문자열의 모든 접미사를 사전식 순서대로 정렬한 배열을 의미합니다. 이는 문자열의 특정 부분을 찾거나, 문자열의 반복 패턴을 찾는 데 매우 유용합니다.

접미사 배열을 생성하는 과정은 다음과 같습니다:

주어진 문자열의 모든 접미사를 생성합니다. 예를 들어, 문자열이 "banana"라면 생성된 접미사는

["banana", "anana", "nana", "ana", "na", "a"]

가 됩니다.

생성된 접미사를 알파벳순으로 정렬합니다. 

정렬된 접미사 배열은 

["a", "ana", "anana", "banana", "na", "nana"]

가 됩니다.

각 접미사에 대응하는 원래 문자열에서의 시작 위치를 저장합니다. 

이렇게 되면 접미사 배열은 

[(5, "a"), (3, "ana"), (1, "anana"), (0, "banana"), (4, "na"), (2, "nana")]

와 같이 표현될 수 있습니다.

 

In Python

def suffix_array(text):
    suffixes = [(text[i:], i) for i in range(len(text))]
    suffixes.sort(key=lambda x: x[0])
    return suffixes

suffix_array('banana')

 

 

 

 

 

좀 더 알고리즘 문제를 해결한다고 하면

LCP 문제 (LCP : Longest Common Prefix)를 찾는 문제를 볼수 있습니다.

 

def lcp(suffixes):
    lcp_arr = []
    for i in range(len(suffixes)-1):
        lcp_val = 0
        suffix1 = suffixes[i][0]
        suffix2 = suffixes[i+1][0]
        while lcp_val < len(suffix1) and lcp_val < len(suffix2) and suffix1[lcp_val] == suffix2[lcp_val]:
            lcp_val += 1
        lcp_arr.append(lcp_val)
    
    max_lcp = max(lcp_arr)  # 최대 LCP 값 찾기
    max_idx = lcp_arr.index(max_lcp)  # 최대 LCP 값의 인덱스 찾기
    return suffixes[max_idx][0][:max_lcp]  # 가장 긴 공통 접미사 반환

suffixes = suffix_array('banana')
lcp(suffixes)

 

 

 

lcp_arr는 접미사 배열의 인접한 요소들 사이에 공통된 접미사의 최대 길이를 저장합니다. 이를 통해 문자열 내에서 가장 긴 반복되는 부분문자열을 찾을 수 있습니다.

위에서 "banana"라는 문자열의 접미사 배열은

[('a', 5), ('ana', 3), ('anana', 1), ('banana', 0), ('na', 4), ('nana', 2)] 입니다.

이 접미사 배열에 대한 LCP 배열을 구하면 [0, 1, 3, 0, 0] 가 됩니다. 이 배열은 "banana"에서 가장 긴 반복되는 부분문자열이 "ana"임을 나타냅니다.