robustflame의 블로그

Suffix Array 접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다. 접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미..