12104번: 순환 순열

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

 

언어 : Kotlin

 

문제 설명 :

두 바이너리 문자열 A와 B가 주어졌을 때, A와 XOR 했을 때, 0이 나오는 B의 순환 순열의 개수를 구하는 프로그램을 작성하시오.

순환 순열이란 순열 P = P0, P1, ..., PN-1이 있을 때, 왼쪽으로 k번 순환 이동시킨 순열이다. 즉, P를 k번 순환 이동 시키면, Pi -> Pi+k mod n 이 된다.

 

입력 :

첫째 줄에 A, 둘째 줄에 B가 주어진다. A와 B의 길이는 105를 넘지 않는 자연수이며, 두 문자열의 길이는 같다.

 

출력 :

첫째 줄에 A와 XOR했을 때, 0이 나오는 B의 순환 순열의 개수를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
101 101	1
111 111	3

 

풀이 : 

단순히 반복문 돌렸다가 시간초과 발생했다.

아마 B의 순환 순열을 구하기 위해 단순히 2배로 길이를 늘린 것을 순회하는데 최대치 105*2를 하나씩 순회해서 그럴 것이라 생각된다.

 

KMP를 사용하여 해결하였다.

중복 제거를 위해 b + b를 하되 마지막 문자를 하나 제거한다.

KMP 알고리즘을 통해 BB에서 A를 찾는다.

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 a = readLine()
    val b = readLine()
    val bb = b + b.substring(0, b.length - 1)

    bw.write("${kmp(bb, a)}")
    bw.flush()
    bw.close()
}

fun kmp(parent: String, pattern: String): Int {
    val table = makeTable(pattern)
    var count = 0
    var idx = 0

    for (i in parent.indices) {
        while (idx > 0 && parent[i] != pattern[idx]) idx = table[idx - 1]
        if (parent[i] == pattern[idx]) {
            if (idx == pattern.length - 1) {
                count++
                idx = table[idx]
            } else {
                idx++
            }
        }
    }

    return count
}

fun makeTable(pattern: String): IntArray {
    val table = IntArray(pattern.length) { 0 }
    var idx = 0

    for (i in 1 until table.size) {
        while (idx > 0 && pattern[i] != pattern[idx]) idx = table[idx - 1]
        if (pattern[i] == pattern[idx]) table[i] = ++idx
    }

    return table
}