Turning quadratic into linear
Expanding around every centre re does work that earlier centres already proved. Manacher algorithm removes that waste, finding the longest palindrome at every centre in time proportional to the string length.
The two unifying tricks
- Uniform centres: insert a separator such as a bar between every character and at the ends. Now every palindrome, originally odd or even, becomes odd length around a single position, so only one case needs handling.
- Mirror reuse: keep track of the rightmost palindrome found so far and its centre. For a new position inside that palindrome, its mirror position on the other side already has a known palindrome radius, which gives a free lower bound for the new position.
Why it stays linear
When a new centre lies inside the current rightmost palindrome, you start its radius from the mirror value instead of from zero. You only ever expand past the rightmost boundary, and that boundary moves forward monotonically. Because total forward movement of the boundary is bounded by the string length, the combined expansion work across all centres is linear.
Key idea
Manacher unifies odd and even palindromes with separators and seeds each centre radius from its mirror inside the rightmost known palindrome; the forward only boundary keeps total expansion linear.