BOJ 13013 - 접미사 배열 2

May 10, 2023

주된 아이디어는 접미사 배열에서 인접한 인덱스들끼리는 그 인덱스의 문자들이 같거나 $1$ 차이난다는 것이다.

즉, 문자가 $n$ 개 쓰인다면 suffix array에서 그 문자들 $n$ 개는 인접한 형태로 등장한다.

suffix array대로 각 위치에 사전순으로 빠른 문자들부터 $0,1,2,3,\dots$ 를 할당한다고 하자.

그럼 처음엔 $\lvert S \rvert$ 만큼 문자가 쓰였다.

이제 계속 인접한 것들을 합쳐가면서 원래 배열과 동일한 배열이 나오는지 구성해본다. $\to$ 브루트포스

항상 $50$ 번이 합쳐지고 각 시도마다 최대 $49$ 번씩 $(0-1, 1-2, …)$ 시도하므로,

멤버 마이어스 알고리즘으로 suffix array를 직접 만든다고 할 때,

$O(N^3 \log ^2N)$ 이 걸린다.

You may also enjoy