접미사 배열 (Suffix Array)

긴 글 하나를 한 번만 전처리해 두면, 그 안에서 어떤 단어든 O(m log n) 만에 찾을 수 있다. 유전체(DNA) 검색, 전문(full-text) 검색 엔진, 표절 탐지의 뼈대가 되는 문자열 자료구조.

1. 접미사란?

문자열 S = "banana" 의 접미사는 각 위치에서 끝까지 잘라낸 조각이다. 길이 n 이면 접미사도 n 개.

i=0  banana
i=1  anana
i=2  nana
i=3  ana
i=4  na
i=5  a

관례상 맨 끝에 그 무엇보다 작은 특수문자 $ 를 붙인다. 그러면 어떤 접미사도 다른 접미사의 접두사가 되지 않아 정렬이 깔끔해진다.

2. 접미사 배열 = 접미사를 정렬한 순서

접미사 문자열을 통째로 저장하면 O(n²) 메모리다. 대신 정렬된 순서의 시작 인덱스만 배열 SA 에 담는다. "banana$" 의 결과:

정렬된 접미사        SA[k]
$                    6
a$                   5
ana$                 3
anana$               1
banana$              0
na$                  4
nana$                2

SA = [6, 5, 3, 1, 0, 4, 2]

3. 패턴 검색 — 정렬 배열에서 이분 탐색

패턴 P 로 시작하는 접미사는 정렬된 SA 안에서 연속 구간을 이룬다. 그 구간의 왼쪽 끝(lower bound) 과 오른쪽 끝(upper bound) 을 각각 이분 탐색으로 찾으면, 구간에 든 SA 값들이 곧 모든 등장 위치다. 비교 한 번에 최대 m 글자를 보므로 O(m log n).

4. LCP 배열 — 이웃 접미사의 공통 접두사

LCP[k] 는 정렬 후 k 번째와 k−1 번째 접미사가 공유하는 가장 긴 공통 접두사 길이다. 이 배열 하나로 여러 문제가 즉답이 된다.

• 가장 긴 반복 부분문자열 = LCP 의 최댓값 위치. "banana$" 는 LCP 최대 3 (ana$ vs anana$) → 반복 문자열 "ana".
• 서로 다른 부분문자열 개수 = n(n+1)/2 − ΣLCP[k].
• 이분 탐색에 LCP 를 곁들이면 검색이 O(m + log n) 까지 빨라진다.

5. 만드는 법과 복잡도

Python — 단순 버전 + 이분 탐색

def build_suffix_array(s):
    s += "$"
    # (접미사, 시작 인덱스) 를 사전순 정렬 → 인덱스만 추출
    return [i for _, i in sorted((s[i:], i) for i in range(len(s)))]

def search(s, sa, p):
    # p 로 시작하는 접미사들의 [lo, hi) 구간을 이분 탐색
    lo, hi, n = 0, len(sa), len(sa)
    while lo < hi:                 # lower bound
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid]+len(p)] < p: lo = mid + 1
        else: hi = mid
    start = lo
    hi = n
    while lo < hi:                 # upper bound
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid]+len(p)] <= p: lo = mid + 1
        else: hi = mid
    return sorted(sa[start:lo])   # 모든 등장 위치

sa = build_suffix_array("banana")
print(sa)                        # [6, 5, 3, 1, 0, 4, 2]
print(search("banana$", sa, "ana"))  # [1, 3]

6. 다른 자료구조와 비교