BOJ 13013 - 접미사 배열 2
주된 아이디어는 접미사 배열에서 인접한 인덱스들끼리는 그 인덱스의 문자들이 같거나 $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)$ 이 걸린다.
Comments