접미사 배열(Suffix Array)은 문자열의 모든 접미사를 사전 순 정렬한 인덱스 배열이다. LCP(Longest Common Prefix) 배열과 함께 사용해 패턴 매칭, 최장 반복 부분문자열 등 다양한 문제를 효율적으로 해결한다.
핵심 개념
문자열 "banana"의 접미사 배열:
접미사: SA[i] LCP[i]
a 5 0
ana 3 1
anana 1 3
banana 0 0
na 4 0
nana 2 2
SA = [5,3,1,0,4,2], LCP = [0,1,3,0,0,2]
O(n log n) SA 구성 (접두사 배가법)
python
def build_suffix_array(s):
n = len(s)
sa = list(range(n))
rank = [ord(c) for c in s]
tmp = [0] * n
k = 1
while k < n:
def cmp_key(i):
r2 = rank[i + k] if i + k < n else -1
return (rank[i], r2)
sa.sort(key=cmp_key)
tmp[sa[0]] = 0
for i in range(1, n):
tmp[sa[i]] = tmp[sa[i-1]]
if cmp_key(sa[i]) != cmp_key(sa[i-1]):
tmp[sa[i]] += 1
rank = tmp[:]
if rank[sa[-1]] == n - 1:
break
k *= 2
return sa
def build_lcp(s, sa):
n = len(s)
rank = [0] * n
for i, v in enumerate(sa):
rank[v] = i
lcp = [0] * n
k = 0
for i in range(n):
if rank[i] == 0:
k = 0
continue
j = sa[rank[i] - 1]
while i + k < n and j + k < n and s[i+k] == s[j+k]:
k += 1
lcp[rank[i]] = k
if k:
k -= 1
return lcp
활용
| 문제 | 방법 |
|---|
| 패턴 매칭 | SA에서 이분 탐색 O(m log n) |
| 최장 반복 부분문자열 | LCP 최대값 |
| 서로 다른 부분문자열 수 | n(n+1)/2 - sum(LCP) |
| 최장 공통 부분문자열 | 두 문자열 연결 후 SA |
관련 개념
