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를 이용하여 해결 할 수 있는 문제가 굉장히 많다.

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