문자열에서 같은 패턴을 한 번만 찾는다면 단순 스캔이나 KMP가 자연스럽습니다. 그러나 하나의 긴 텍스트에 대해 서로 다른 패턴을 반복해서 조회하고, 출현 횟수와 위치 범위, 두 접미사의 공통 접두 길이까지 함께 다뤄야 한다면 접미사 배열과 LCP(Longest Common Prefix)를 분리해 구축하는 편이 유리합니다. 접미사 배열은 원문의 각 시작 위치를 사전순으로 정렬한 배열이고, LCP 배열은 그 정렬에서 이웃한 두 접미사가 몇 글자나 공유하는지 기록합니다. 검색은 접미사 배열의 연속 구간을 찾는 일이고, 임의 접미사 비교는 LCP의 구간 최솟값을 묻는 일로 바뀝니다.
접미사와 사전순 순서
문자열 banana의 접미사는 다음과 같습니다.
| 시작 위치 | 접미사 |
|---|---|
| 0 | banana |
| 1 | anana |
| 2 | nana |
| 3 | ana |
| 4 | na |
| 5 | a |
이를 사전순으로 정렬하면 a(5), ana(3), anana(1), banana(0), na(4), nana(2)가 되므로 suffix array는 [5, 3, 1, 0, 4, 2]입니다. 배열의 값은 정렬된 문자열 자체가 아니라 원문에 대한 시작 offset이라는 점이 중요합니다. 패턴 ana를 찾을 때도 배열의 인덱스가 1과 2라는 뜻이 아니라 원문의 위치 3과 1을 가리킨다는 계약을 유지해야 합니다.
접미사 두 개와 패턴을 비교할 때는 원문의 끝에 먼저 도달하는 경우를 명시해야 합니다. 패턴이 접미사의 접두이고 접미사가 더 짧다면, 예를 들어 na와 nan을 비교할 때 na를 더 작은 문자열로 봅니다. 반대로 접미사와 패턴의 비교가 패턴 길이만큼 같다면 그 접미사는 패턴과 일치하는 후보입니다. 이 “패턴의 모든 글자가 접미사 앞부분과 같다”는 판정과, 완전한 사전순 비교를 섞지 않아야 경계가 흔들리지 않습니다.
Doubling 구성과 순위 상태
접미사를 실제 문자열로 정렬하면 비교 비용이 반복되어 커집니다. doubling 방식은 길이 1, 2, 4, …인 앞부분의 순위를 이용해 두 배 길이의 순위를 만들고, 동일한 쌍을 정렬합니다. 한 단계에서 접미사 i의 키는 (rank[i], rank[i+step])이며 두 번째 항이 문자열 끝을 넘으면 별도의 작은 sentinel 순위로 취급합니다. 새 순위가 모두 달라지거나 비교 길이가 n 이상이 되면 종료합니다. 각 단계의 순위 쌍을 counting/radix 정렬로 선형 시간에 정렬하면 전체 O(n log n) 시간과 선형 보조 공간을 얻습니다. 매 단계 일반 비교 정렬을 사용하면 O(n log² n)이 될 수 있으므로 doubling이라는 이름만으로 시간 상한을 정하지 않습니다.
예를 들어 banana에서 길이 1의 문자 순위가 a=0, b=1, n=2라고 하겠습니다. 시작 위치 1의 길이 2 키는 (a,n)=(0,2), 위치 3의 키는 (a, n)=(0,2)이므로 아직 같은 순위입니다. 길이 4 단계에서는 위치 1이 (rank[1], rank[3]), 위치 3이 (rank[3], rank[5])를 갖고 두 번째 반쪽이 달라져 순서가 갈립니다. 여기서 계산하는 것은 suffix array 자체뿐 아니라 각 원문 위치의 rank 역배열입니다. 이후 LCP를 계산하려면 rank[start]를 suffixArray의 위치로 즉시 찾아야 하므로 두 배열을 함께 보관하는 편이 명확합니다.
그림을 글로 읽기
- 원문 banana: 시작 offset 0..5 · 접미사 생성
- suffix array: [5, 3, 1, 0, 4, 2] · 사전순 순위
- rank 역배열: rank[1] = 2 · offset → 순위
- 인접 LCP: [1, 3, 0, 0, 2] · 순위 사이 공유 길이
- 패턴·suffix 질의: 경계 또는 RMQ · 위치를 원문 offset으로 변환
- 원문 banana → suffix array: doubling 정렬
- suffix array → rank 역배열: 역매핑
- suffix array → 인접 LCP: 인접 비교
- 인접 LCP → 패턴·suffix 질의: 최솟값·경계
- rank 역배열 → 패턴·suffix 질의: 순위 조회
Kasai LCP의 재사용
LCP 배열의 정의를 LCP[r] = lcp(SA[r-1], SA[r])로 잡으면 첫 원소에는 대응하는 값이 없습니다. 따라서 banana의 배열 [5,3,1,0,4,2]를 실제로 비교하면 인접 접미사 쌍은 a와 ana의 1, ana와 anana의 3, anana와 banana의 0, banana와 na의 0, na와 nana의 2가 되어 LCP[1..5]=[1,3,0,0,2]입니다. 구현에서 LCP를 LCP[r]에 둘지 LCP[r-1]에 둘지는 뒤의 RMQ 구간과 함께 고정해야 합니다.
Kasai 알고리즘은 원문 위치를 왼쪽에서 오른쪽으로 훑습니다. rank[i]=r이고 r이 마지막 순위가 아니라면 j=SA[r+1]인 다음 접미사와 직접 비교합니다. 이전 원문 위치 i-1에서 비교 길이를 h까지 얻었다면, S[i..]와 S[j..]를 비교하기 전에 h-1부터 시작할 수 있습니다. 이전 비교에서 처음 h글자가 같았다면 두 문자열에서 첫 글자를 제거한 부분은 적어도 h-1글자 같기 때문입니다.
이 값은 매 원문 위치마다 1씩 줄어들 수 있고, 새로 확장될 때만 증가합니다. h가 전체 순회에서 증가하는 총량은 최대 선형이고, 감소도 위치마다 한 번씩 일어나므로 전체 문자 비교가 O(n)으로 제한됩니다. 마지막 suffix처럼 다음 순위가 없는 경우에는 비교하지 않고 h=0으로 내려야 합니다. 이를 누락하면 다음 반복에서 존재하지 않는 SA[r+1]를 읽거나, 다음 비교의 시작 길이를 잘못 재사용할 수 있습니다.
작은 상태를 따라가면 원문 i=1에서 suffix anana와 다음 순위의 banana는 공통 접두가 0이므로 h=0입니다. i=3에서 ana와 순위 다음의 anana를 비교해 h=3을 얻었다고 합시다. 다음 원문 위치 i=4에서는 na와 그 다음 순위의 nana를 비교하므로 h를 2부터 시작하고, 두 글자를 확인한 뒤 LCP=2를 기록합니다. h를 매번 0으로 재설정해도 결과는 맞지만 반복되는 접두 비교가 누적되어 선형 시간 보장을 잃습니다.
패턴 검색과 두 경계
패턴 P와 접미사 배열을 비교해 P보다 사전순으로 작은 접미사와 그렇지 않은 접미사의 경계를 찾으면 lower bound를 얻습니다. 이어서 P를 접두로 갖는 접미사보다 큰 첫 위치를 찾으면 upper bound가 됩니다. banana에서 P=ana이면 SA 순서의 접미사 표기는 a, ana, anana, banana, na, nana입니다. ana로 시작하는 것은 배열 위치 1과 2의 두 개이므로 [1,3) 구간이고, 원문 위치로 바꾸면 {3,1}입니다.
한 번의 일치 발견으로 멈추면 존재 여부는 알 수 있지만 출현 수는 알 수 없습니다. lower bound를 l, upper bound를 r라고 할 때 출현 수는 r-l이고, 구간의 각 SA[k]가 실제 시작 위치입니다. 패턴이 빈 문자열이면 모든 접미사가 일치한다고 볼지, 길이 0 검색을 금지할지 API에서 정해야 합니다. 이 노트의 검색 계약에서는 빈 패턴을 별도 입력 오류로 거절하는 것이 안전합니다. 또한 패턴이 접미사보다 길어지는 비교에서 접미사 끝을 정상적인 작은 종료로 처리해야 합니다.
패턴 비교 자체는 한 접미사에서 최대 |P|글자를 볼 수 있고, 이진 탐색을 두 번 하므로 단순한 구현의 상한은 O(|P| log n)입니다. LCP를 이용해 탐색 중 이미 확인한 공통 길이를 재사용하는 최적화는 별도 구현이며, 단순히 LCP 배열이 있다고 해서 이진 탐색이 자동으로 O(log n)이 되는 것은 아닙니다. 반복 질의에서 텍스트가 고정되어 있고 패턴이 많다면 전처리 O(n log n)과 O(n) 저장 비용을 질의 비용과 분리해 판단합니다.
임의 suffix LCP와 RMQ
두 시작점 i, j의 rank를 각각 r1, r2라 하고 r1<r2라고 합시다. 두 접미사 사이에 있는 인접 접미사들의 공통 접두 길이 중 최소값이 전체 두 접미사의 LCP입니다. 위의 정의처럼 LCP[r]가 SA[r-1]와 SA[r]의 LCP라면 질의 구간은 LCP[r1+1..r2]입니다. 예를 들어 rank 2와 5를 비교하면 LCP[3], LCP[4], LCP[5]를 최소화합니다. r1을 포함하면 rank 1과 2 사이의 값을 잘못 섞게 됩니다.
같은 suffix를 비교하는 경우에는 배열 길이에서 시작 offset을 뺀 suffix 길이를 반환하는 편이 자연스럽습니다. 서로 다른 suffix에 대해서만 RMQ 구간이 생기며, rank 순서가 반대이면 두 rank를 먼저 swap합니다. sparse table은 정적 LCP의 O(1) 질의를 위해 사용할 수 있지만 O(n log n) 공간이 필요하고, segment tree는 갱신 여지가 있는 모델에서 O(log n) 질의와 더 작은 전처리 공간을 선택할 수 있습니다. 어떤 RMQ 구조를 골라도 r1+1과 r2의 포함 범위 테스트를 먼저 고정해야 합니다.
서로 다른 부분 문자열과 선택 기준
모든 suffix 길이의 합은 n(n+1)/2이지만 같은 부분 문자열이 여러 suffix의 접두로 반복됩니다. suffix array 순서에서 각 suffix가 앞선 suffix들과 공유하는 가장 긴 접두는 바로 직전까지의 최대 LCP이며, 인접 LCP의 합으로 중복을 빼면 됩니다. 따라서 서로 다른 부분 문자열 수는
n(n+1)/2 - sum(LCP[1..n-1])
입니다. aba의 suffix 길이는 3, 2, 1이어서 총 6이고, 정렬 a, aba, ba의 인접 LCP는 1, 0이므로 결과는 5입니다. sentinel을 실제 문자열의 문자로 포함했다면 그 suffix 길이와 LCP를 계산에서 제외해야 합니다.
검색만 하고 텍스트가 계속 바뀐다면 suffix array는 갱신 비용이 크므로 KMP, Z, rolling hash, trie 같은 구조가 더 적절할 수 있습니다. 반대로 고정 텍스트에 많은 패턴, 접미사 간 비교, distinct substring 계산이 함께 필요하면 한 번 만든 SA와 LCP를 여러 질의가 공유합니다. 해시와 달리 SA/LCP 비교는 구조의 비교 규칙 아래 결정적이지만, 전처리와 메모리 배치 비용이 있습니다. 유니코드 텍스트라면 바이트 단위인지 코드 포인트 단위인지 먼저 고정하고, 정렬·비교·offset 반환 단위를 모두 같은 모델로 맞춰야 합니다.
검증 항목과 참고 범위
구현 검증은 banana처럼 중복 접두를 가진 문자열, 모든 문자가 같은 문자열, 빈 문자열, 한 글자, 패턴이 텍스트보다 긴 경우를 포함해야 합니다. 각 suffix를 실제 문자열로 정렬한 기준 결과와 SA를 대조하고, Kasai 결과는 모든 인접 쌍을 직접 비교한 배열과 대조합니다. 임의 두 rank에 대해서는 직접 LCP와 RMQ 결과를 전수 비교하고, 검색 결과는 단순 startswith 스캔과 위치 집합을 비교합니다. 이 문서에서 제시한 표와 계산은 설명용 수기 계산이며 로컬 실행 결과로 주장하지 않습니다.
근거로 확인한 cp-algorithms의 Suffix Array 문서는 doubling 구성의 시간·공간 분석, 이진 탐색 기반 부분 문자열 검색, Kasai의 선형 LCP 계산과 인접 LCP를 이용한 비교를 설명합니다. 해당 페이지는 2024-08-02 갱신본이며 번호가 붙은 라이브러리 버전이나 특정 프로그래밍 언어의 실행 계약은 제시하지 않습니다. RMQ의 질의 상한은 선택한 sparse table·segment tree 등에 따라 달라지므로 여기서는 구조별 전형적 비용으로 범위를 나누어 설명했습니다.
참고 URL
- https://cp-algorithms.com/string/suffix-array.html — 접미사 배열 doubling, 이진 탐색, Kasai LCP 및 distinct-substring 식을 확인한 알고리즘 참고 페이지입니다. RMQ의 구체 비용은 선택한 자료구조에 따라 달라집니다.