Suffix Array와 LCP

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하는 방법이다. 자세한 설명은 코드를 게시하는 것으로 대신하겠다.

#include <vector> #include <algorithm> using namespace std; #define MAXN 500005 int N,SA[MAXN]; char S[MAXN]; void SuffixArray() { int i,j,k; int m = 26; // 처음 알파벳 개수 vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0); for (i=1;i<=N;i++) cnt[x[i] = S[i]-'a'+1]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[i]]--] = i; for (int len=1,p=1;p<N;len<<=1,m=p){ 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; for (i=0;i<=m;i++) cnt[i] = 0; for (i=1;i<=N;i++) cnt[x[y[i]]]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i]; swap(x,y); p = 1; x[SA[1]] = 1; for (i=1;i<N;i++) x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p; } }

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)$인 알고리즘이 있다. 코드는 아래와 같다.

#include <vector> using namespace std; #define MAXN 500005 int N,SA[MAXN],lcp[MAXN]; char S[MAXN]; void LCP() { int i,j,k=0; vector <int> rank(N+1,0); for (i=1;i<=N;i++) rank[SA[i]] = i; for (i=1;i<=N;lcp[rank[i++]]=k) for (k?k--:0,j=SA[rank[i]-1];S[i+k]==S[j+k];k++); }

연습 문제: BOJ 9248

#include <stdio.h> #include <string.h> #include <vector> using namespace std; #define MAXN 500005 int N; int SA[MAXN],lcp[MAXN]; char S[MAXN]; void SuffixArray() { int i,j,k; int m = 26; vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0); for (i=1;i<=N;i++) cnt[x[i] = S[i]-'a'+1]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[i]]--] = i; for (int len=1,p=1;p<N;len<<=1,m=p){ 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; for (i=0;i<=m;i++) cnt[i] = 0; for (i=1;i<=N;i++) cnt[x[y[i]]]++; for (i=1;i<=m;i++) cnt[i] += cnt[i-1]; for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i]; swap(x,y); p = 1; x[SA[1]] = 1; for (i=1;i<N;i++) x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p; } } void LCP() { int i,j,k=0; vector <int> rank(N+1,0); for (i=1;i<=N;i++) rank[SA[i]] = i; for (i=1;i<=N;lcp[rank[i++]]=k) for (k?k--:0,j=SA[rank[i]-1];S[i+k]==S[j+k];k++); } int main() { int i; scanf("%s",S+1); N = strlen(S+1); SuffixArray(); LCP(); for (i=1;i<=N;i++) printf("%d ",SA[i]); printf("\nx"); for (i=2;i<=N;i++) printf(" %d",lcp[i]); puts(""); }

끝으로, 접미사 배열과 LCP를 이용하여 해결 할 수 있는 문제가 굉장히 많다.

예) 최장 공통 부분 문자열, 부분문자열의 가장 큰 등장값

저작자표시

'공부' 카테고리의 다른 글

Majority Vote Algorithm  (2)	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)  (7)	2014.07.25