접미사 배열

접미사 배열(Suffix Array)은 어떤 문자열의 모든 접미사를 사전순으로 정렬해 둔 배열입니다.

이를 구하기 위해 문자열의 접미사들을 모아놓은 뒤 정렬을 하게 되면

길이가 N인 문자열의 접미사의 개수는 N개 이므로 O(NlgN)번 비교연산을 진행하지만

string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에 시간복잡도가 O(N^2 lgN)입니다.

이 때 좀 더 빠르게 접미사 배열을 만들기 위하여 맨버-마이어스 알고리즘을 사용합니다.

접미사들의 특성을 이용하여 매번 접미사를 첫 한글자, 두글자, 네글자, 여덟글자... 기준으로 정렬하며

매번 이전 정렬에서 얻은 정보를 이용하여 두 문자열을 빠르게 대소 비교합니다.

이러한 과정으로 진행하면 비교연산을 O(lgN)번으로 줄일 수 있으며

이 알고리즘으로 접미사 배열을 만드는 시간 복잡도는 O(Nlg^2N)입니다.

또한 같이 사용하는 LCP 배열(Longest Common Prefix Array)은

접미사 배열에서의 인접한 접미사와의 가장 긴 공통 접두사의 길이를 가지고 있는 배열입니다.

이는 접미사의 특성을 이용하여 O(N)번 만에 구할 수 있습니다.

접미사 배열과 LCP 배열은 여러가지 문자열 응용 문제를 풀 수 있는 도구가 되기에 중요한 문자열 알고리즘입니다.

기본 문제

9248번: Suffix Array

11478번: 서로 다른 부분 문자열의 개수