13322번 - 접두사 배열

문제

접미사 배열(suffix array)이란, 어떤 문자열의 모든 접미사를 사전 순으로 정렬한 뒤, 각 접미사의 시작 위치를 기록한 배열을 의미한다. 예를 들어 'banana' 라는 문자열에 대해 접미사 배열을 구한다면 아래와 같다

1. 문자열의 모든 접미사는 아래와 같다.
   • banana, anana, nana, ana, na, a
2. 위 접미사들을 사전 순으로 정렬하면 아래와 같다.
   • a, ana, anana, banana, na, nana
3. 각 접미사의 원래 문자열에서의 시작 인덱스를 기록하면 아래와 같다.
   • 5, 3, 1, 0, 4, 2

따라서 문자열 'banana'의 접미사 배열은 { 5, 3, 1, 0, 4, 2 } 가 된다.

연세대학교의 PS 동아리 모르고리즘 회원 택희와 남규는 문자열 문제 하나를 같이 풀어보고 있었다. 다음은 그 과정에서 있었던 대화의 일부를 발췌한 것이다.

• 택희 : 이거 그냥 suffix array 구해놓고 풀면 되겠는데?
• 남규 : suffix array면.. 접미사 배열 구하고 뒤집으면 되나?
• 택희 : ??
• 남규 : ??
• 택희 : suffix가 접미사인데?
• 남규 : 아 맞네.. 접두사로 착각했네.
• 택희 : 근데 그럼 접두사 배열은 어떻게 구하지?
• 남규 : 그러게?
• 택희 : 문자열 뒤집고 suffix array 구하면 되나? 아닌데..?

택희와 남규는 혼란에 빠졌다.

혼란스러워하는 택희와 남규를 위해 접두사 배열을 구해 줄 프로그램을 작성해 보자.

입력

첫 줄에 알파벳 소문자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 100000)

출력

|S|줄에 걸쳐, 문자열 S의 모든 접두사를 사전 순으로 정렬했을 때, 목록의 첫 접두사부터 마지막 접두사까지 각 접두사가 끝나는 인덱스를 순서대로 출력한다. 문자열의 인덱스는 0부터 시작한다.

제한

힌트