1893번: 시저 암호

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

 

언어 : Kotlin

 

문제 설명 :

암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리우스 시저의 이름을 딴 것이다. 시저 암호는 대치 암호의 한 종류로써, 원문의 각 글자가 어떤 일정한 수만큼의 뒷 순서의 알파벳으로 대체되는 방식이다. (단, Z의 다음 알파벳은 A로 한다) 예를 들어, 대문자 알파벳의 일반적인 순서를 따르면서 3만큼 시프트(이동) 시키면, A는 D로 대체되고, B는 E로, C는 F로... 그런 식으로 변환되어서 마지막 X, Y, Z는 다시 A, B, C로 대체된다. 이런 식으로 알파벳 순서에서 X만큼 뒤로 옮기는 암호화 방법의 "시프트 값"을 X라고 하겠다.

당신에게 어떤 알파벳 순서 A, 원문 W, 시저 암호화된 문자열 S가 주어진다.

암호문을 해독했을 때 그 해독한 문자열에서 원문이 단 한 번만 나타난다고 할 때, 암호화 할 때 쓰였다고 추측 가능한 시프트 값을 ([0,|A|-1] 범위에서) 모두 찾아라.

 

입력 :

입력의 첫 줄에는 테스트 케이스의 수를 의미하는 정수 N이 있다. 각 테스트 케이스는 알파벳의 순서 A, 원문 W, 암호문 S가 3줄에 걸쳐 순서대로 쓰여 있다. 알파벳 순서 A는 알파벳 소문자, 대문자, 그리고 숫자만을 포함하며, 이 순서는 사전순이 아닐 수도 있다 (예제 입력의 3번째 테스트 케이스를 참고하라). A의 모든 문자는 다르다.

입력 범위 : 3 <= |A| <= 62, 1 <= |W| <= 50,000, 3 <= |S| <= 500,000.

 

출력 :

각 테스트 케이스에 대해 1줄씩 출력한다. 만약 해독된 암호문에서 원문이 단 한번만 등장하게 하는 암호화 방법이 존재하지 않는다면, 즉 조건을 만족하는 암호문의 시프트 값이 존재하지 않는다면 "no solution"을 출력한다 (따옴표 제외). 만약 오직 하나의 시프트 값만이 조건을 만족한다면, "unique: #" (단, #는 조건을 만족하는 시프트 값) 을 출력한다 (따옴표 제외). 만약 조건을 만족하는 시프트 값이 여러 개 존재한다면, "ambiguous: " 를 출력하고 그 뒤에 오름차순으로 정렬된 조건을 만족하는 시프트 값의 목록을 출력한다.

자세한 사항은 예제 출력을 참고하라.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
4 ABC ABC ABCBBBABC ABC ABC ABCBCAABC D7a D7a D7aaD77aDD7a ABC ABC ABC	no solution unique: 1 ambiguous: 1 2 unique: 0

 

풀이 : 

시저 암호의 원리를 이용해 주어진 암호문을 해독하고 원문이 단 한 번만 나타나는 시프트 값을 찾는 문제.

각 테스트 케이스마다 가능한 모든 시프트 캆을 적용해 암호문을 해독해보고 비교해야한다.

 

입력받은 알파벳 순서에 따라 문자의 인덱스를 매핑하고 decrypt 함수를 통해 주어진 시프트 값을 기준으로 암호문을 해독한다. 단, 암호문 - 원문 비교 시프트값을 전부 시행하게 될 경우 시간초과가 발생한다.

 

따라서 단순히 반복문을 사용하여 문자열을 검색하지 않고, KMP 알고리즘을 사용한다.

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

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

    repeat(readLine().toInt()) {
        val alphabet = readLine()
        val word = readLine()
        val cipher = readLine()

        val shiftMatches = mutableListOf<Int>()
        val indexMap = mutableMapOf<Char, Int>()
        for (i in alphabet.indices) indexMap[alphabet[i]] = i

        for (shift in alphabet.indices) {
            val decrypted = decrypt(shift, cipher, indexMap, alphabet)
            val cnt = kmpSearch(word, decrypted)

            if (cnt == 1) shiftMatches.add(shift)
        }

        val result = when (shiftMatches.size) {
            0 -> "no solution"
            1 -> "unique: ${shiftMatches[0]}"
            else -> "ambiguous: ${shiftMatches.joinToString(" ")}"
        }

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

fun decrypt(shift: Int, cipher: String, indexMap: MutableMap<Char, Int>, alphabet: String): String {
    val length = alphabet.length
    val sb = StringBuilder()

    for (c in cipher) {
        val idx = (indexMap[c]!! - shift + length) % length
        sb.append(alphabet[idx])
    }

    return sb.toString()
}

fun kmpSearch(pattern: String, text: String): Int {
    val m = pattern.length
    val n = text.length

    val lps = IntArray(m)
    var j = 0
    var i = 1

    while (i < m) {
        if (pattern[i] == pattern[j]) {
            j++
            lps[i] = j
            i++
        } else {
            if (j != 0) {
                j = lps[j - 1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }

    var count = 0
    i = 0
    j = 0

    while (i < n) {
        if (pattern[j] == text[i]) i++.also { j++ }

        if (j == m) {
            count++
            j = lps[j - 1]
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) j = lps[j - 1] else i++
        }
    }

    return count
}