티스토리 뷰
Suffix Array
접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다.
접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미사중 하나가 다른 하나를 포함하고 있기 때문에 이전 정렬에서 얻은 정보를 이용해서 두 접미사의 대소 비교를 \(O(1)\)에 수행한다.
구현
위의 알고리즘에서는 정렬 시에 보통의 \(O(Nlog_2N)\) 알고리즘을 사용하지만, 선형 시간복잡도를 가지는 계수 정렬(Counting Sort)를 이용하면, 아래와 같이 접미사 배열을 만드는 총 시간복잡도를 \(O(Nlog_2N)\)로 줄일 수 있다.
Longest Common Prefix Array
접미사 배열과 함께 자주 사용되는 것이 있는데 바로 LCP 배열이다. Longest Common Prefix, 말 그대로 가장 긴 공통 접두사를 의미하는데, 여기서 말하는 LCP 배열은 (사전순으로 정렬되어 있는) 접미사 배열에서 이전 접미사와의 최장 공통 접두사의 길이를 저장한다. 문자열, 그 문자열의 접미사 배열, 그리고 LCP 배열의 관계는 아래 표를 보면 이해하기가 쉽다.
i |
suffixArray[ i ] |
suffix |
LCP[ i ] |
0 |
5 |
a |
|
1 |
3 |
ana |
1 |
2 |
1 |
anana |
3 |
3 |
0 |
banana |
0 |
4 |
4 |
na |
0 |
5 |
2 |
nana |
2 |
LCP 배열은 접미사 배열에서 사전상으로 인접한 두 접미사의 최장 공통 접두사의 길이를 하나 하나 세면 되지만, 이 방식은 \(O(N^2)\)의 시간이 소요되는 방식이다. 이 LCP 배열을 계산하는 보다 효율적인 \(O(N)\) 알고리즘이 존재하는데 그 핵심 아이디어는 접미사 배열을 계산할 때와 마찬가지로 한 접미사는 다른 접미사의 접미사라는 점을 이용하여 중복된 계산을 줄이는 것이다.
i | suffixArray[ i ] | suffix | LCP[ i ] |
0 | 5 | a |
|
1 | 3 | ana | 1 |
2 | 1 | anana | 3 |
3 | 0 | banana | 0 |
4 | 4 | na | 0 |
5 | 2 | nana | 2 |
위의 접미사 배열에서 인접한 접미사 "ana"와 "anana"의 LCP는 3이라는 것을 계산했다고 하자. 그 후에 "na", "nana"의 LCP를 계산하려고 할 때, 한 가지 사실을 알 수 있다. 이미 "ana"와 "anana"의 LCP는 3이라고 계산해두었기 때문에 앞의 a가 없는 "na"와 "nana"의 LCP는 최소 2라는 사실이다. (보다 자세한 내용은 여기를 참고하면 될 것 같다.)
즉, S[i..], 그리고 S[i..]와 사전상으로 인접한 접미사(접미사 배열상 바로 이전 접미사)와의 LCP를 \(m\)이라고 하면, S[i+1..], S[i+1..]와 사전상으로 인접한 접미사의 LCP는 최소 \(m-1\) 이므로 이 부분은 중복하여 계산하지 않아도 된다.
구현
예제
참고 자료
- JMBOOK, 구종만
- Competitive Programming 3, Steven Halim & Felix Halim
- http://jason9319.tistory.com/141
- http://blog.naver.com/dark__nebula/220419358547
'알고리즘 이론' 카테고리의 다른 글
Modular Arithmetic (0) | 2017.03.18 |
---|---|
탐색 (Searching) (0) | 2017.03.06 |
Counting Sort, Radix Sort (0) | 2017.02.23 |
트리의 지름 (Diameter of Tree) (0) | 2017.02.20 |
KMP Pattern Searching (0) | 2017.02.20 |
- Total
- Today
- Yesterday
- suffix array
- Data structure
- divide and conquer
- kmp search
- pattern matching
- BFS
- greedy
- Square root decomposition
- Segment Tree
- sort
- sliding window
- Fenwick Tree
- search
- math
- Strings
- implementation
- Binary search
- tree
- Graph
- branch and bound
- Minimum Spanning Tree
- constructive algorithms
- Heap
- parametric search
- Dynamic Programming
- karatsuba
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |