3356번: 라디오 전송

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

 

언어 : Kotlin

 

문제 설명 :

라디오 방송국은 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받게 하기 위해서 메시지를 계속해서 반복 전송한다.

한 청취자가 받은 메시지가 주어진다. 항상 청취자가 받은 메시지의 길이는 방송국에서 보낸 메시지의 길이보다 크거나 같다. 이때, 라디오 방송국에서 보낸 메시지를 구하는 프로그램을 작성하시오.

즉, 입력으로 S가 주어졌을 때, S가 S' + S' + ... + S'의 부분 문자열이 되는 가장 짧은 부분수열 S'를 구하는 프로그램을 작성하시오. 

 

입력 :

첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000)

 

출력 :

첫째 줄에 S'의 길이 L'을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
8 cabcabca	3

 

풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

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

    val l = readLine().toInt()
    val s = readLine()

    val pi = getPi(s)
    bw.write("${l - pi[pi.lastIndex]}")

    bw.flush()
    bw.close()
}

fun getPi(str: String): IntArray {
    val pi = IntArray(str.length)
    var j = 0

    for(i in 1 until str.length) {
        while(j > 0 && str[i] != str[j]) j = pi[j - 1]
        if(str[i] == str[j]) pi[i] = ++j
    }

    return pi
}