Manacher's Algorithm
목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학기가 시작되어 모든 알고리즘들을 한번씩 보면서 넘어가던 도중 사람들이 잘 관심 가지지 않지만, 알아두면 재미있을법한 알고리즘인 Manacher’s Algorithm 을 소개해보고자 한다. Manacher’s Algorithm은 String 내에 존재하는 모든 Palindrome을 $O(N)$에 구하는 강력한 알고리즘이다. 물론 이 알고리즘이 실전에 출제되는 경우는 매우 드물지만 원리 자체가 재미있고 시간복잡도가 $O(N)$이 되는 원리가 재미있는 알고리즘이므로 자세하게 설명해보고자 한다. 팰린드롬 팰린드롬을 모르는 사람을 위해 간단히...