티스토리 뷰
Suffix Array (접미사 배열)
Suffix Array(韓: 접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 문자열 관련된 문제에서 자주 쓰이는 방법이다.
예를 들어, 문자열 $S = banana$가 있다고 하자. 문자열 $S$의 접미사들은 아래와 같다.
suffix |
i |
banana |
1 |
anana |
2 |
nana |
3 |
ana |
4 |
na |
5 |
a |
6 |
문자열 $S$의 접미사 배열은 아래와 같다.
suffix | i |
a | 6 |
ana | 4 |
anana | 2 |
banana | 1 |
na | 5 |
nana | 3 |
접미사 배열에서 문자열을 배열로 가지고 있으면 공간복잡도가 $O(N^2)$이기 때문에 접미사를 나타내는 정수 $i$를 가지고 있는다. 즉, "banana"의 접미사 배열은 [6,4,2,1,5,3] 이다.
접미사 배열을 구하는 가장 쉬운 방법은 단순히 정렬하는 방법이다. 문자열의 사전순 비교에 드는 시간은 $O(N)$이며, 항이 $N$개 있으므로, 정렬하는 시간복잡도는 $O(N^2 \lg N)$이다.
접미사 배열을 구하는 빠른 알고리즘 중 가장 알려진 알고리즘은 $O(N \lg N)$이다. Pang Ko와 Srinivas AluruJuha, Petuha Kärkkäinen와 Peter Sanders 등등 $\Theta(N)$만에 구하는 알고리즘도 개발되었지만, 경시에서 사용될 만큼 통용되진 않았다. 경시 문제에서는 $O(N \lg N)$ 보다 빠른 시간복잡도를 요구하는 문제는 안나온다고 볼 수 있다.
접미사 배열을 $O(N \lg N)$만에 구하는 방법은 길이를 1, 2, 4, 8, … 로 증가하면서 counting sort하는 방법이다. 자세한 설명은 코드를 게시하는 것으로 대신하겠다.
LCP (Longest Common Prefix)
접미사 배열 자체만으로 해결할 수 있는 문제는 거의 없다. 접미사 배열과 함께 중요한 개념인 LCP (Longest Common Prefix)를 소개하겠다. LCP의 뜻은 가장 긴 공통 접두사로 일반적으로 그 길이에 의미가 있다. 대부분의 상황에서 Suffix Array에 쓰이는 개념이라고 볼 수 있다.
lcp[i]는 접미사 배열의 $i$번째 접미사와 $i-1$번째 접미사의 가장 긴 공통 접두사의 길이라고 정의된다. "banana"의 접미사 배열과 lcp 값은 아래와 같다.
suffix | i | lcp |
a | 6 | x |
ana | 4 | 1 |
anana | 2 | 3 |
banana | 1 | 0 |
na | 5 | 0 |
nana | 3 | 2 |
이 때, $1 < i \leq N$인 모든 $i$에 대해 lcp[i] 값을 계산하는 시간복잡도가 $O(N)$인 알고리즘이 있다. 코드는 아래와 같다.
연습 문제: BOJ 9248
끝으로, 접미사 배열과 LCP를 이용하여 해결 할 수 있는 문제가 굉장히 많다.
예) 최장 공통 부분 문자열, 부분문자열의 가장 큰 등장값
'공부' 카테고리의 다른 글
Majority Vote Algorithm (1) | 2016.06.23 |
---|---|
Grundy Number (0) | 2014.11.13 |
Suffix Array와 LCP (14) | 2014.08.14 |
Manacher's Algorithm (0) | 2014.08.13 |
중국인의 나머지 정리와 확장 유클리드 알고리즘 (0) | 2014.07.25 |
고속 푸리에 변환 (Fast Fourier Theorem, FFT) (6) | 2014.07.25 |
-
rlatkddn212 정리 잘해주셔서 감사해요.
ㅎㅎ 제가 이해 한게 맞다면 LCP 부분에서 값이 틀린것 같아요?..
x13022 라고 되어있는데 x13002 아닐까요? 2014.11.04 18:05 -
전명우 확인이 늦어서 죄송합니다. 즉시 수정하겠습니다. 2014.11.10 02:12 신고
-
skawlsdlf51 ㅎㅎ 2014.11.04 20:00
-
bowbowbow SuffixArray를 얻는 코드에서 x와 y의 정의가 뭔지 질문드려도 될까요? 2016.04.10 14:34 신고
-
SA공부하고있는사람 저도 이게 좀 궁금합니다.
문자열 S가 "banana" 일때를 예를들어
매 반복마다 x,y,SA 의 변화를 적어가며
파악해보려했지만 정확하게 파악하기가 쉽지가않네요. 2016.12.17 10:42 -
깜장호랭 좋은 코드를 발견하여, 살펴 보고 분석하고 있습니다. x가 rank입니다. 여기서의 index가 S의 index이고 해당하는 lcp 구할 때 rank에 해당합니다. 즉, i로 시작하는 suffix의 rank값이 x에 저장됩니다. SA는 이것의 inverse라고 보시면 됩니다. order라고 할까요? 'banana' 스트링의 SA값은 6,4,2,1,5,3이 될텐데요. 즉, 테이블의 값이 됩니다. 저는 이 코드들을 0으로 시작하는 배열로 변경하여 사용하고 있습니다. 2017.10.13 14:38
-
전명우 대신 답해주셔서 감사합니다. 2017.11.03 18:06 신고
-
학생 for (int len=1,p=1;p<N;len<<=1,m=p){
에서
<<= 뜻이 뭐에요 .. 2016.08.08 18:49 -
전명우 비트연산자 입니다. 2016.08.17 05:22 신고
-
니켈 혹시 LCP 구하는부분에서
S[i+k]==S[j+k];k++ 이부분이 왜 상수시간안에 해결될 수 있는지 이해가 안되네요 ㅠㅠ
최악의 경우 O(N) 이 걸릴것 같은데... 혹시 이부분에 대해서 설명해주실 수 있으신가요? 2018.07.02 12:29 -
전명우 Line 15에 있는 for문이 상수시간에 돌아간다는 말이 아닙니다. Line 14, 15에 있는 이중for문의 총 시간복잡도가 O(N)이라는 말입니다. 이는 i+k의 값이 시간이 지남에 따라 절대 감소하지 않는다는 것과 i+k의 값이 N보다 커지지 않아 k++이 되는 횟수가 최대 N임을 통해 증명 가능합니다. 2018.07.27 16:15 신고
-
이승재 for (p=0,i=N-len;++i<=N;) y[++p] = i;
for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
이 부분 소스에 대해 더 자세히 설명 가능할까요?
제가 추측한 바로는, 이전에 구한 SA를 가지고 다음 counting sort할 때, 우선순위를 정해주는거 같은데.. 맞는지 잘 모르겠습니다.
이걸 바탕으로 저 두개의 for문을 이해하려 하는데 잘 안되네요 2019.07.27 13:19 -
건이두 연습문제 BOJ 9248의 링크가 404 에러로 나오네요.
확인해 보니까, URL의 마지막 글자 / 를 지우면 해당 문제로 갈 수 있습니다. 2020.02.24 12:12 신고 -
전명우 감사합니다. 수정했습니다. 2020.09.04 20:11 신고
- Total
- 199,306
- Today
- 0
- Yesterday
- 66
- idea
- vote
- Greedy Method
- IOI2012
- z-trening
- majority
- Boyer
- Divide & Conquer
- dynamic programming
- moore
- Parametric Search
- Dynamic Pramming
- USACO
- IOI2014
- Dijkstra
- IOI2011
- Tree
- TRIE
- BOI
- BOI 2001
- HackerRank
- IOI2013
- Boyer-Moore Majority Vote Algorithm
- optimization
- Splay Tree
- Knuth Optimization
- Segment tree
- ioi
- BOI 2009
- Algorithm