13275번: 가장 긴 팰린드롬 부분 문자열

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

 

언어 : Kotlin

 

문제 설명 :

문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

 

출력 :

가장 긴 팰린드롬 부분 문자열의 길이를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
abcd	1
abab	3
dcabccd	2
abcba	5
aaaaa	5

 

풀이 : 

https://small-stepping.tistory.com/986

14444번: 가장 긴 팰린드롬 부분 문자열

위 문제와 완전히 같은 문제이다.

이전에 못 풀고 넘어갔었다가 마나커 알고리즘을 알게된 후 풀 수 있게 되었다.

 

https://small-stepping.tistory.com/987

마나커(Manacher) 알고리즘

 

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 sb = StringBuilder()
    val input = readLine()
    for (c in input) {
        sb.append("#")
        sb.append(c)
    }
    sb.append("#")

    val list = MutableList(sb.length) { 0 }
    manachers(sb.toString(), list)

    var result = -1
    for (i in list.indices) {
        result = maxOf(result, list[i])
    }

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

fun manachers(text: String, list: MutableList<Int>) {
    val length = text.length
    var r = 0
    var c = 0

    for (i in 0 until length) {
        if (r < i) list[i] = 0 else list[i] = minOf(list[2 * c - i], r - i)
        while (i - list[i] - 1 >= 0 && i + list[i] + 1 < length && text[i - list[i] - 1] == text[i + list[i] + 1]) list[i]++

        if (r < i + list[i]) {
            r = i + list[i]
            c = i
        }
    }
}