1701번: Cubeditor

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

1701번: Cubeditor

언어 : Kotlin

 

문제 설명 :

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

 

입력 :

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

 

출력 :

입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

 

제한 사항 :

• 시간 제한 : 0.5초
• 메모리 제한 : 128MB

입출력 예 :

입력	출력
abcdabcabb	3
abcdefghijklmn	0
abcabcabc	6

 

풀이 : 

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 max = 0
    val input = readLine()
    for (i in input.indices) {
        val temp = input.substring(i, input.length)
        max = max.coerceAtLeast(kmp(temp))
    }

    bw.write("$max")
    bw.flush()
    bw.close()
}

fun kmp(temp: String): Int {
    var max = 0
    var cur = 0
    val arr = IntArray(temp.length) { 0 }
    for (i in 1 until temp.length) {
        while (cur > 0 && temp[cur] != temp[i]) cur = arr[cur - 1]
        if (temp[cur] == temp[i]) {
            arr[i] = ++cur
            max = max.coerceAtLeast(arr[i])
        }
    }

    return max
}