Suffix Array와 LCP

Suffix Array(SA)란 접미사(suffix)들을 정렬해놓은 배열이다. 매우 단순하게 생각하면, 길이가 $1, 2, ..., N$인 suffix를 모두 만든 후 정렬하면 된다. 그러면 $O(N^2logN)$에 구할 수 있다. 그러나 Suffix Array는 $O(N)$ 또는 $O(NlogN)$에 구할 수 있다. 선형 풀이는 복잡하기 때문에 여기서는 $O(NlogN)$만 다루겠다. 

 

Suffix Array를 빠르게 구하는 기본 아이디어는, 정렬하려는 문자열들이 서로의 suffix이어서 이전 결과를 이용할 수 있다는 것이다. 길이  $p$까지를 고려하여 suffix들을 정렬한 결과를 가지고 있을 때, 그 값들을 이용하면 길이 $2p$까지를 고려한 결과를 얻을 수 있다. 문자열 $[a, a+2p)$과 문자열 $[b, b+2p)$를 비교하는 것은 $[a, a+p)$와 $[b, b+p)$를 비교한 결과와 $[a+p, a+2p)$와 $[b+p, b+2p)$를 비교한 결과를 이용해 구할 수 있기 때문이다. 구체적으로는, $[a+p, a+2p)$와 $[b+p, b+2p)$를 비교하여 정렬을 한 뒤 그 결과를 고려하여(stable sort) $[a, a+p)$와 $[b, b+p)$에 대해 다시 정렬을 한다. 정렬을 quick sort 등으로 하면 $O(Nlog^2N)$에 SA를 구할 수 있고, counting sort를 하면 $O(NlogN)$에 구할 수 있다. 

 

LCP(Longest Common Prefix)는 Suffix Array 상에서 연속해있는 두 suffix가 prefix를 몇 글자 공유하는지이다.  LCP를 빠르게 구하는 아이디어는, ($\textrm{suffix }[i+1, N)\textrm{의 lcp}) \geq (\textrm{suffix }[i, N)\textrm{의 lcp})-1$이라는 것이다.

 

아래 링크를 보고 공부하였다.

https://blog.myungwoo.kr/57

https://koosaga.com/125 

 

내 코드

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10010;

int N;				// S의 길이
char S[MAXN];			// SA와 lcp를 구할 문자열
int sfx[MAXN], rev[MAXN], lcp[MAXN];
int aux[MAXN], nrev[MAXN], cnt[MAXN];

void get_sfx() {		// S의 SA를 sfx에 저장하고, 그 역을 rev에 저장한다
	for(int i = 0; i < N; i++) rev[i] = S[i] - 'a' + 1;
	for(int i = 0; i < N; i++) sfx[i] = i;
	
	rev[N] = nrev[N] = 0;
	int pnt = 1, p = 1;
	while(1) {		// 앞쪽 p개의 문자만 보고 정렬한 순서가 rev에 들어있는 상태
    		// p~2p-1 번째 문자를 보고 정렬한 결과
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0; i < N; i++) cnt[rev[min(i + p, N)]]++;
		for(int i = 1; i <= 26 || i <= N; i++) cnt[i] += cnt[i - 1];
		for(int i = N - 1; i >= 0; i--) aux[--cnt[rev[min(i + p, N)]]] = i;	
        
        	// 0~p-1번째 문자도 고려하여 정렬(0~2p-1 고려)
		memset(cnt, 0, sizeof(cnt));
		for(int i = 0; i < N; i++) cnt[rev[i]]++;
		for(int i = 1; i <= 26 || i <= N; i++) cnt[i] += cnt[i - 1];
		for(int i = N - 1; i >= 0; i--) sfx[--cnt[rev[aux[i]]]] = aux[i];	
        			
		if(pnt == N) break;
		pnt = 1;
		nrev[sfx[0]] = 1;
		for(int i = 1; i < N; i++) {					
        	// nrev 값을 구하며 suffix들이 몇 가지로 나뉘었는지 구분
			if(rev[sfx[i - 1]] != rev[sfx[i]] || rev[sfx[i - 1] + p] != rev[sfx[i] + p])
				pnt++;
			nrev[sfx[i]] = pnt;
		}
		memcpy(rev, nrev, sizeof(rev));
		p *= 2;
	}
	for(int i = 0; i < N; i++) rev[sfx[i]] = i;	// sfx의 역을 구한다
}

void get_lcp() {					// S의 SA sfx가 구해져있는 상태에서 lcp를 구한다
	int h = 0;
	for(int i = 0; i < N; i++) {			// 길이가 긴 suffix부터 보며 lcp를 구한다
		if(rev[i]) {
			int prv = sfx[rev[i] - 1];
			while(S[prv + h] == S[i + h]) h++;
			lcp[rev[i]] = h;
		}
		if(h) h--;			// 다음 suffix의 lcp는 h-1 이상이다
	}
	lcp[N] = 0;
}