Algorithm
[Algorithm] 맨버-마이어스 알고리즘(Suffix Array)
접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미사들을 만들어준다. 만들어진 접미사들을 맨 앞글자를 기준으로 정렬한다. 이후 정렬 기준을 앞에서 2번째 문자, 3번째 문자 ... 로 늘려가면서 최대 문자열의 길이인 n번째 문자까지 바꿔가며 정렬을 진행한다. 위의 과정을 따르면, 한번 정렬을 진행하는데 $O(n log n)$ 만큼의 시간이 걸리고, 정렬을 최대 문자열의 길이만큼 반복한다고 했으므로 총 시간복잡도는 $O(n^2 log n)$ 과 같이 나타날 것이다. 이를 맨버-마이어스 알고리즘을 통해 $O(n log^2 n)$의 시간복잡도로 단축시킬수 있다. 이제 정렬이 ..
