3033번: 가장 긴 문자열

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

3033번: 가장 긴 문자열

언어 : Kotlin

 

문제 설명 :

상근이는 꿈에서 길이가 L인 문자열을 외웠다.

꿈에서 깬 상근이는 이 문자열을 종이에 적었다. 종이를 적던 중에 어떤 문자열은 두 번 이상 등장하는 것 같은 느낌을 받았다.

문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것을 찾는 프로그램을 작성하시오. (부분문자열은 겹쳐서 등장할 수도 있다)

 

입력 :

첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다.

 

출력 :

첫째 줄에 두 번 이상 등장하는 부분 문자열 중 길이가 가장 긴 것의 길이를 출력한다. 만약 그러한 문자열이 없을 때는 0을 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
11 sabcabcfabc	3
18 trutrutiktiktappop	4
6 abcdef	0

 

다른사람의 풀이 : 

https://devbelly.tistory.com/34

[백준 3033] 가장 긴 문자열

 

+++

이분탐색과 라빈카프 알고리즘 사용

모듈러 2개 사용하여 해시값이 같다면 단순 비교를 건너뛰고 같다고 판단

base와 mod 설정 시, base는 서로 다른 문자의 개수보다 큰 숫자 사용. mod는 매우 큰 소수를 사용.

해당 문제에선 소문자만 등장하므로 base는 26보다 큰 31을 사용

+++

 

길이 m인 문자열이 두 번 이상 등장할 경우, m보다 작은 n이 두 번 이상 등장하는지 알 수 있는가 하면, 그렇다.

예를 들어 문자열 aabaa에서 부분 문자열 aa는 2번 등장하고, 더 짧은 a는 aa가 등장한 인덱스를 제외하고도 더 등장할 수 있다.

 

그러할때 길이 m 보다 긴 길이 k는 몇 번 등장할 수 있을까? 운이 좋다면 m이 등장한 만큼 등장하겠으나, 적어도 m이 등장한 횟수보단 적을 것이다. 이러한 관찰을 통해 등장 횟수가 길이에 반비례함을 알 수 있다. 즉, 등장횟수가 정렬되어 있으므로 이분 탐색 전략을 취한다는 것.

 

남은 문제는 길이 m이 주어졌을 때, 두 번 이상 등장함을 판단해야하므로 KMP 알고리즘을 제외한 일대일 매칭 알고리즘인 라빈카프 알고리즘을 사용한다. 시간복잡도는 이분탐색 + 라빈카프 이므로 O(N log N)이다

 

------

 

해당 문제를 통해 라빈카프 알고리즘에 대해 찾아봤고, 어떻게 돌아가는 알고리즘인지 파악했으나, 라빈카프 알고리즘은 기본적인 형태로는 전체 문자열 A와 비교할 패턴 문자열 B 두개가 주어지고, 비교할 패턴 문자열 B의 길이를 알아야하는 상태였다.

 

하지만 이 문제에선 직접 부분 문자열을 찾아 대조해보며 해야했고, 문자열이 길기 때문에 무턱대고하는건 시간초과 메모리초과가 당연지사해보였다. 도움을 받은 풀이는 C++이지만, C++을 알아보기 어려웠기에 다른 풀이를 찾아봐도 Kotlin과 가장 유사한 언어인 Java 풀이를 찾을 수 없었고, 알아보기 쉬운 Python 풀이도 보이지 않았기 때문에 더욱 이해가 어려웠다.

 

그러나 풀이에서 공통적으로 보이는 설명인 라빈 카프 알고리즘과 길이가 k인 문자열이 2번 반복된다면 항상 길이가 k보다 작은 문자열이 최소 2번 이상 반복된다는 성질을 이용한다는 내용이다. (위에서도 설명되어 있지만, 예를들어 abcabc에서 abc가 2번 이상 반복된다면 abc의 부분 문자열인 ab 또한 항상 2번 이상 반복된다는 것.)

 

해당 성질을 이용하면 패턴 문자열의 길이를 이분 탐색으로 결정할 수 있다는 것이었다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

val mod = intArrayOf(100000000 + 7, 1000000000 + 9)
val longs1 = LongArray(2)
val longs2 = LongArray(2)
val set = HashSet<Long>()
const val base = 31

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

    val n = readLine().toInt()
    val str = readLine()

    val arr = IntArray(3) { 0 }.also { it[1] = n }
    while (arr[0] <= arr[1]) {
        val mid = (arr[0] + arr[1]) shr 1
        if (rabinKarp(mid, str, n)) {
            arr[2] = mid
            arr[0] = mid + 1
        } else {
            arr[1] = mid - 1
        }
    }

    bw.write("${arr[2]}")
    bw.flush()
    bw.close()
}

fun rabinKarp(m: Int, str: String, n: Int): Boolean {
    set.clear()
    for (i in 0..1) {
        longs1[i] = 1L
        longs2[i] = str[0].code.toLong()
    }
    for (i in 1 until m) {
        for (j in 0..1) {
            longs2[j] = (longs2[j] * base + str[i].code.toLong()) % mod[j]
            longs1[j] = (longs1[j] * base) % mod[j]
        }
    }
    set.add((longs2[0] shl 32) or longs2[1])
    for (i in m until n) {
        for (j in 0..1) {
            longs2[j] = ((longs2[j] - (str[i - m].code.toLong() * longs1[j]) % mod[j] + mod[j]) % mod[j])
            longs2[j] = (longs2[j] * base + str[i].code.toLong()) % mod[j]
        }
        val key = (longs2[0] shl 32) or longs2[1]
        if (!set.contains(key)) set.add(key) else return true
    }

    return false
}