선형 시간의 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]$은 이미 정렬되어 있으므로 상수 시간에 바로 비교할 수 있다.

모든 시간을 합하면 $SA(N)=SA(\frac{2}{3}N)+O(N)$이고, 등비수열의 합이므로 $SA(N)=O(N)$이 된다.