16900번: 이름 정하기

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

 

언어 : Kotlin

 

문제 설명 :

욱제는 새로 산 컴퓨터에 이름을 붙이려고 한다.

새로 산 컴퓨터의 이름은 욱제가 가장 좋아하는 문자열인 S가 최소 K번 부분 문자열로 등장해야 한다. 가능한 이름이 여러가지면 길이가 가장 짧아야 한다.

S와 K가 주어졌을 때, 욱제가 새로 산 컴퓨터 이름의 길이를 구해보자.

 

입력 :

첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다.

 

출력 :

첫째 줄에 욱제가 새로 산 컴퓨터 이름의 길이를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
ada 3	7
abc 2	6
r 7	7
rr 5	6
abbababbbbababababba 2	36
abcabcabca 3	16

 

풀이 : 

kmp 알고리즘에서 사용하는 makeTable.

pi((접두 == 접미)의 최장길이)를 사용해서 해결 가능한 문제.

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))

    val (s, k) = readLine().split(" ")
    val pi = getPi(s)

    var result = s.length.toLong()
    for (i in 1 until k.toInt()) {
        result += s.length - pi[s.length - 1]
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}

fun getPi(s: String): IntArray {
    val pi = IntArray(s.length)
    var begin = 1
    var matched = 0

    while (begin + matched < s.length) {
        if (s[begin + matched] == s[matched]) {
            matched++
            pi[begin + matched - 1] = matched
        } else {
            if (matched == 0) {
                begin++
            } else {
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]
            }
        }
    }

    return pi
}