백준 16900 이름 정하기 Kotlin (kmp)

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

16900번: 이름 정하기

문제

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

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

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

입력

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

출력

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

알고리즘 분류

• 문자열
• kmp
• z

풀이

kmp 관련 문제들은 다 티어가 높다.

kmp 알고리즘을 제대로 이해하고 있다면 쉬운 문제인데, 내가 처음 kmp 알고리즘을 공부할 때 이해하기 어려웠던 것을 생각하면 그럴만하다.

 

문제를 풀기 전, kmp에 대해 먼저 공부하길 바란다.

이 문제는 kmp 알고리즘의 실패 함수를 이용해 접두사와 접미사가 일치하는 길이를 찾으면 된다.

이를 저장할 배열을 pi라고 하는데 생각해보니 왜 pi지?

본인은 table이라는 배열에 저장했다.

예제 6번인

abcabcabca에 실패 함수를 실행한 결과는

0001234567이다.

즉 접두사와 접미사가 일치하는 길이가 최대 7이라는 얘기다.

 

우리가 찾는 값은 abcabcabca가 3번 나오는 문자열의 길이이다.

abcabcabca를 pattern이라 하고,

찾을 문자열을 x라 할 때,

x = abcabcabca 이면 현재 pattern이 한 번 등장했다.

여기서 접두사==접미사 최대 길이만큼 점프하고 남은 만큼만 추가하면 pattern을 한 번 더 만들 수 있다.

x = abcabcabca + bca

여기서 또 접두사==접미사 최대 길이만큼 점프하고 남은 만큼만 추가하면 pattern을 한 번 더 만들 수 있다.

x = abcabcabca + bca + bca

결과적으로 x = abcabcabcabcabca로 길이가 16일 때, 3번의 pattern을 등장시킬 수 있다.

즉 정답은

pattern의 길이 + (pattern의 길이 - 접미사==접두사의 최대 길이) * (k-1)가 된다.

 

 

코드

val br = System.`in`.bufferedReader()

fun makeTable(pattern : String) : IntArray{
    val table = IntArray(pattern.length)
    var j=0
    for(i in 1 until table.size){
        while(j>0 && pattern[i] !=pattern[j]){
            j = table[j-1]
        }
        if(pattern[i]==pattern[j]){
            table[i] = ++j
        }
    }
    return table
}

fun main() = with(System.out.bufferedWriter()){
    val (pattern, str) = br.readLine().split(' ')
    val k = str.toLong()
    val table =  makeTable(pattern)
    write("${pattern.length+(pattern.length-table[table.size-1])*(k-1)}")
    close()
}