13322번: 접두사 배열

문제 출처 : https://www.acmicpc.net/problem/13322

 

언어 : Kotlin

 

문제 설명 :

접미사 배열(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부터 시작한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
ab	0 1

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    readLine().forEachIndexed { index, c ->
        bw.appendLine("$index")
    }
    bw.flush()
    bw.close()
}