[BOJ] 16163 #15164번_제보 - P5

문제풀이

1. manacher 알고리즘을 사용하여 각 위치에서의 가장 긴 팰린드롬 문자열의 길이 구하기
2. sum((팰린드롬 문자열의 길이 + 1) / 2)가 팰린드롬 부분 문자열의 개수이다.

---

주의사항

---

소요시간

10분

---

package 백준.Platinum.P5.p16163_15164번_제보

import kotlin.math.min

fun main() {
    val S = readln().asSequence().joinToString("#", "#", "#")
    val A = IntArray(S.length)
    var p = 0
    var r = 0
    for (i in S.indices) {
        A[i] = if (i <= r) min(A[2 * p - i], r - i) else 0
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < S.length && S[i - A[i] - 1] == S[i + A[i] + 1]) A[i]++
        if (r < i + A[i]) {
            r = i + A[i]
            p = i
        }
    }
    println(A.sumOf { (it + 1).toLong() / 2 })
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p16163_15164%EB%B2%88_%EC%A0%9C%EB%B3%B4/p16163_15164%EB%B2%88_%EC%A0%9C%EB%B3%B4.kt

---

문제링크

https://www.acmicpc.net/problem/16163