PS 이야기

Suffix Array (접미사 배열) Suffix Array(韓: 접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 문자열 관련된 문제에서 자주 쓰이는 방법이다. 예를 들어, 문자열 $S = banana$가 있다고 하자. 문자열 $S$의 접미사들은 아래와 같다. suffix i banana 1 anana 2 nana 3 ana 4 na 5 a 6 문자열 $S$의 접미사 배열은 아래와 같다. suffixia6ana4anana2banana1na5nana3 접미사 배열에서 문자열을 배열로 가지고 있으면 공간복잡도가 $O(N^2)$이기 때문에 접미사를 나타내는 정수 $i$를 가지고 있는다. 즉, "banana"의 접미사 배열은 [6,4,2,1,5,3] 이다. 접미사 배..