(알고리즘) 원형 문자열

길이가 n(n<=40000)인 문자열을 끝과 끝이 연결된 원형으로 써보자.
이 문자열은 항상 시계방향으로 읽는데, 시작위치가 어디인지는 정해져 있지 않으므로 n가지 방법으로 읽을 수 있습니다.
이 중 사전순으로 가장 앞에오는 문자열은 무엇일까요?

이 문제를 푸는 가장 단연한 방법은 n개의 후보를 하나하나 만들어보고 이들 중 가장 사전순으로 앞에 오는 것을 찾는 것이다. 그러면 n-1번의 비교를 하게 되는데, 각 비교에는 O(n)의 시간이 걸리기 때문에 전체시간복잡도는 O(n^2)이 된다.


접미사배열을 통해 이 문제를 풀 수 있다.

문자열 S를 두 번 반복한 2S를 만드는것이다. 따라서 2S의 접미사 배열을 우선만든뒤, 길이가 n이상인 접미사중 가장 앞에 오는 것을 찾아내면 되는 것이다.
그러면 접미사배열을 만드는 시간인 O(nlg^2n)시간에 답을 계산 할 수 있다.