13264번: 접미사 배열 2

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

 

언어 : Kotlin

 

문제 설명 :

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

각각의 접미사는 시작하는 문자의 번호를 이용해서 정수로 나타낼 수 있다. 예를 들어, baekjoon은 0번 접미사이고, joon은 4번 접미사이다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 접미사 번호를 출력하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 100,000보다 작거나 같다.

 

출력 :

첫째 줄부터 S의 접미사를 사전순으로 접미사 번호를 한 줄에 하나씩 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
abcdabcabb	7 4 0 9 8 5 1 6 2 3

 

풀이 : 

멘버 마이어스 알고리즘을 사용한다.

 

https://small-stepping.tistory.com/936

멘버 마이어스 알고리즘과 Kasai 알고리즘

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

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

    val str = readLine()
    bw.write(getSuffixArray(str).joinToString("\n"))
    bw.flush()
    bw.close()
}

fun getSuffixArray(input: String): ArrayList<Int> {
    val n = input.length
    var t = 1
    val perm = ArrayList<Int>()
    var group = IntArray(n + 1)

    for (i in 0 until n) {
        perm += i
        group[i] = input[i] - 'a'
    }

    group[n] = -1

    val compareUsing2T = CompareUsing2T(n, t, group)
    while (t < n) {
        Collections.sort(perm, compareUsing2T.comparator())
        t *= 2
        if (t >= n) break

        val newGroup = IntArray(n + 1).also {
            it[perm[0]] = 0
            it[n] = -1
        }

        for (i in 1 until n) {
            if (compareUsing2T.comparator().compare(perm[i - 1], perm[i]) < 0) newGroup[perm[i]] = newGroup[perm[i - 1]] + 1
            else newGroup[perm[i]] = newGroup[perm[i - 1]]
        }

        group = newGroup
        compareUsing2T.changeValues(t, group)
    }

    return perm
}

class CompareUsing2T(private val n: Int, private var t: Int, private var group: IntArray) {
    fun changeValues(t: Int, group: IntArray) {
        this.t = t
        this.group = group.copyOf(group.size)
    }

    fun comparator() = Comparator<Int> { o1, o2 ->
        if (group[o1] != group[o2]) return@Comparator group[o1] - group[o2]

        var left = o1 + t
        var right = o2 + t

        if (o1 + t > n) left = n
        if (o2 + t > n) right = n

        group[left] - group[right]
    }
}