The goal
We want the longest palindromic substring, or the palindrome radius at every center. Checking each center by expanding outward is simple but can repeat work, so Manacher removes that repetition.
Handling even and odd
Palindromes can have odd or even length. Manacher inserts a filler character such as a sentinel between every pair of characters, so every palindrome becomes odd length and a single uniform method handles both cases.
Mirroring known radii
The algorithm tracks the rightmost palindrome found so far, given by a center and a right boundary. For a new center inside that boundary:
- Its mirror across the center gives an initial radius for free.
- We cap that radius at the boundary, then expand only if it reaches the edge.
This reuse is what makes the whole scan linear.
After the scan
Each transformed center yields a radius. Mapping back to the original string recovers the true palindrome lengths, and the largest radius locates the longest palindromic substring.
Key idea
Manacher pads the string for uniform odd palindromes and mirrors radii across the rightmost known palindrome, computing every center radius in a single linear pass.