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

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

 

언어 : Kotlin

 

문제 설명 :

알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 알파벳 소문자로만 이루어진 문자열 S가 주어진다. S의 길이는 100,000을 넘지 않는다.

 

출력 :

첫째 줄에 S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 출력한다.

 

제한 사항 :

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

 

입출력 예 :

입력	출력
abab	3
banana	5
baekjoon	2
online	1
eevee	5

 

풀이 : 

마나허 알고리즘을 사용하였다.

문자열에 존재하는 팰린드롬 부분 문자열을 빠르게 찾을 수 있는 알고리즘이다.

문자열에서 팰린드롬 부분 문자열을 찾을 때 시작점이나 끝점을 고정하면 굉장히 복잡해지기에 일반적으로 중심을 고정하고 좌우 문자를 비교한다. 또한 그냥 중심을 고정하면 길이가 짝수인 팰린드롬을 찾을 수 없기에 처음에 각각 문자들 사이에 동일한 문자(일반적으로 "#")를 하나씩 집어 넣는다. 이렇게 하여 짝수 팰린드롬도 찾을 수 있게 된다.

 

https://m.blog.naver.com/jqkt15/222108415284

[알고리즘] Manacher’s Algorithm - 마나커(마나허) 알고리즘

https://00ad-8e71-00ff-055d.tistory.com/91

89. 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
        }
    }
}