[BOJ] 13275 가장 긴 팰린드롬 부분 문자열 - P5

문제풀이

1. manacher 알고리즘 사용

---

주의사항

---

소요시간

20분

---

package 백준.Platinum.P5.p13275_가장긴팰린드롬부분문자열

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) {
        if (i <= r) A[i] = min(A[2 * p - i], r - i)
        else A[i] = 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.max())
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p13275_%EA%B0%80%EC%9E%A5%EA%B8%B4%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC%EB%B6%80%EB%B6%84%EB%AC%B8%EC%9E%90%EC%97%B4/p13275_%EA%B0%80%EC%9E%A5%EA%B8%B4%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC%EB%B6%80%EB%B6%84%EB%AC%B8%EC%9E%90%EC%97%B4.kt

---

문제링크

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

---

회고

manacher 알고리즘을 학습할 수 있었다.