선형 시간의 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$를 하나의 문자로 보고 새.. 더보기 이전 1 ··· 3 4 5 6 7 8 9 ··· 24 다음