4354번: 문자열 제곱

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

4354번: 문자열 제곱

언어 : Kotlin

 

문제 설명 :

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

a^0 = "" (빈 문자열)
a^(n+1) = a*(a^n)
문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

 

입력 :

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

 

출력 :

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

 

제한 사항 :

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

입출력 예 :

입력	출력
abcd aaaa ababab .	1 4 3

 

풀이 : 

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

    var input = readLine()
    while (input != ".") {
        val last = makeTable(input)
        val remain = input.length % (input.length - last)
        val div = input.length / (input.length - last)
        bw.appendLine("${if (remain == 0) div else 1}")

        input = readLine()
    }
    bw.flush()
    bw.close()
}

fun makeTable(str: String): Int {
    val table = Array(str.length) { 0 }
    var idx = 0
    for (i in 1 until str.length) {
        while (idx > 0 && str[i] != str[idx]) idx = table[idx - 1]
        if (str[i] == str[idx]) table[i] = ++idx
    }

    return table.last()
}