(알고리즘) 접미사배열 알고리즘

*접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다.

대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다.

예제) 접미사 배열을 이용한 검색

짚더미 H가 바늘 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용합니다. 예를들어, "alohomora"에서 "homo"를 찾는다고 합시다. "homo"는 S의 접미사인 "homora"의 접두사가 된다. 모든 부분 문자열에 대해 이 속성이 성립함을 쉽게 알 수 있다.
이 속성을 이용하면 H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다. 접미사 배열의 길이는 항상 |H|이므로 이진탐색의 내부내는 O(lg|H|)번 수행된다.

각 문자열 비교에 O(|N|)시간이 걸리기 때문에 이 이진 탐색의 수행시간은 O(|N|lg|H|)이 된다. 물론 전처리 과정에서 짚더미의 접미사 배열을 생성해야 한다는 부담이 있지만, 같은 짚더미에서 여러 바늘을 찾아야 한다면 이 알고리즘은 아주유용하다.


<접미사 배열 생성>

sort의 시간복잡도는 O(nlogn)이다. 이거은 두 원소의 비교에 상수 시간이 걸릴 때 이야기이다. 두 문자열을 비교하는데는 최대 두 문자열의 길이에 비례하는 시간이 걸리므로, 한 번 비교에 O(n)시간이 걸린다고 할 수 있다.
전체 시간 복잡도는 O(n^2*log(n))이다.
이 시간 복잡도가 크다고 생각할 수 도 있지만,실제로는 모든 글자를 다 비교할 필요없이 첫 몇글자만 비교해도 어느 쪽이 큰지 판단 할 수 있는 경우가 많다.