선형 시간의 suffix array construction

suffix array는 문자열 $S$ 의 $N=length(S)$ 개의 모든 접미사를 사전순으로 정렬한 배열으로, $O(N)$ 시간과 $O(N)$ 메모리에 구할 수 있다. suffix array를 로그 시간에 구하는 방법을 안다면, 이해하기 어렵지 않을 것 같다.

길이 $x$ 의 문자열의 suffix array를 구하는데 걸리는 시간을 $SA(x)$ 라고 하자.

일단 $S$ 에 있는 모든 문자보다 작은 문자 $a$ 를 잡아서 $S$ 뒤에 3개 붙이고, $T_i$ ( $0\leq i\leq N$ )를 $S[i\cdots i+2]$ 로 정의하자.

일단 $T_i$ 들을 정렬해서 $T_i$ 가 각각 사전순으로 몇 번째인지 구하자. radix sort를 사용하면 $O(N)$ 에 정렬할 수 있다.

각각의 $T_i$ 를 하나의 문자로 보고 새로운 문자열 $T=T_1T_4T_7\cdots T_2T_5T_8\cdots$ 를 정의하자.

$length(T)\leq \frac{2}{3}N$ 이므로, $T$ 의 suffix array를 구하는데는 $SA(\frac{2}{3}N)$ 의 시간이 걸린다.

$T$ 의 suffix array를 이용하면, $S[i\cdots N-1]$ ( $i\neq 3k$ )들을 모두 정렬할 수 있다.

이제 $S[i\cdots N-1]$ ( $i=3k$ )들을 모두 정렬하자. $S[3i]\neq S[3j]$ 라면 첫 글자 기준으로 정렬하면 된다. $S[3i]=S[3j]$ 라면 $S[3i+1\cdots N-1]$ 의 사전순 순서를 알고 있으므로 그걸 이용해서 정렬하면 된다. radix sort를 사용하면 $O(N)$ 에 정렬할 수 있다.

마지막으로 정렬된 두 배열을 합치면 된다. 두 배열이 모두 정렬되어 있으므로 두 원소를 $O(1)$ 에 비교할 수 있다면 $O(N)$ 에 merge가 가능하다.

$i$ , $j$ 가 mod 3으로 다르다면, $k(\leq 2)$ 가 존재하여 $i+k$ , $j+k$ 가 모두 mod 3으로 0이 아니다. 따라서 앞의 2개 이하의 원소만 하나씩 비교하면, $S[i+k\cdots N-1]$ , $S[j+k\cdots N-1]$ 은 이미 정렬되어 있으므로 상수 시간에 바로 비교할 수 있다.