[BOJ] 17844 복붙하기 - P2

TaeGN·2024년 9월 9일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

64/114

문제풀이

이분 탐색을 통해 문자열의 길이를 정한다.
해당 문자열의 길이에 해당하는 해시값을 라빈-카프 알고리즘을 사용하여 효율적으로 구한다.
해시 충돌을 방지하기 위해 서로 다른 모듈러 연산을 통해 해시값을 4개정도 사용한다.

주의사항

해시 충돌이 발생할 수 있다는 것을 고려해야 한다.

소요시간

1시간

package 백준.Platinum.P2.p17844_복붙하기

import kotlin.math.sqrt

val mod = longArrayOf((1L shl 31) - 1, 1_000_000_007, 1_000_000_009, 998244353)
val power = mod.map { (26 until sqrt(it.toDouble()).toInt()).random() }

class Hash(val arr: LongArray) {
    override fun equals(other: Any?): Boolean {
        if (other is Hash) return arr.contentEquals(other.arr)
        return super.equals(other)
    }

    override fun hashCode(): Int {
        return arr.contentHashCode()
    }
}

fun main() {
    val S = readln()
    val primeArr = Array(mod.size) { LongArray(S.length).apply { this[0] = 1 } }
    for (i in mod.indices) {
        for (j in 1 until S.length) {
            primeArr[i][j] = primeArr[i][j - 1] * power[i] % mod[i]
        }
    }

    fun isPossible(len: Int): Boolean {
        if (len == 0) return true
        val map = mutableMapOf<Hash, Int>()
        val hash = LongArray(mod.size)
        for (i in S.indices) {
            if (i >= len) {
                for (j in mod.indices) {
                    hash[j] = (hash[j] + (mod[j] - (S[i - len] - 'a') * primeArr[j][len - 1] % mod[j])) % mod[j]
                }
            }
            for (j in mod.indices) {
                hash[j] = (hash[j] * power[j] + (S[i] - 'a')) % mod[j]
            }
            val nHash = Hash(hash.copyOf())
            if (i >= len - 1) {
                if (i - map.getOrDefault(nHash, S.length) >= len) return true
                if (nHash !in map) map[nHash] = i
            }
        }
        return false
    }

    fun search(start: Int = 0, end: Int = S.length): Int {
        val mid = (start + end) / 2
        if (start == mid) return if (isPossible(end)) end else start
        return if (isPossible(mid)) search(mid, end)
        else search(start, mid - 1)
    }
    println(search().let { if (it == 0) -1 else it })
}