~/home/let the mirror do the work: manacher’s algorithm
Algorithm · Strings
Let the Mirror Do the Work.
Don't memorize Manacher's algorithm — watch the mirror do the work. To find the longest palindrome in a string, first slip a separator between every character so every palindrome becomes odd-length, then measure a radius at each center. The magic is a cached rightmost palindrome [C, R]: for a new center inside it, an earlier mirror already knows the answer, so you reuse it for free and only compare fresh characters past the edge. That turns O(n²) into O(n).
insert # separators · radius per center · mirror inside [C, R] · O(n)
LONGEST PALINDROME
The longest substring that reads the same forwards and backwards.
# TRANSFORM
Put a separator between every char so even and odd palindromes are both odd.
RADIUS P[i]
How far the palindrome centered at i reaches — and its length in the original string.
MIRROR + [C, R]
Inside the rightmost palindrome, reuse P[2C − i] instead of expanding again.
manacher.sim — longest palindrome of "abaaba"
Ready
The string is padded to #a#b#a#a#b#a# so every palindrome has a real center. Each P[i] is the palindrome radius there. The amber [C, R] box caches the furthest-right one; inside it we mirror. Press Step.
i < R: P[i] = min(R − i, P[2C − i]); then expand past R
—
Center i
0
Best radius
Two palindromes for the price of one
The naive way to find the longest palindrome is to stand at every possible center and expand outward while the characters match. There are about 2n centers and each can expand up to n, so it is O(n²). Manacher keeps that expand-around-center idea but refuses to redo work. It tracks the palindrome that currently reaches furthest right, as a center C and right edge R. Now consider a new center i sitting inside that window. Everything in [C, R] mirrors around C, so the character pattern at i matches the pattern at its mirror i' = 2C − i — whose radius you already computed. You copy that radius, capped so it cannot poke outside the window (you have no guarantee beyond R), and only then try to expand further. Every successful expansion pushes R right, and R only moves forward, so all the expansions together cost O(n).
01
Transform
Insert # between every character and at the ends, so all palindromes are odd and centered on a real index.
02
Keep the rightmost palindrome
Maintain C and R: the center and right edge of the palindrome reaching furthest right.
03
Mirror, then expand
For i < R, start from P[i] = min(R − i, P[2C − i]), then expand character by character.
04
Slide and finish
If the palindrome at i passes R, set C = i, R = i + P[i]. The max P[i] is the answer.
Time
O(n)
Space
O(n)
Naive
O(n²)
Idea
Mirror + window
To recover the substring, note that in the padded string P[i] equals the palindrome length in the original, and its start is (i − P[i]) / 2. For abaaba the biggest radius is 6, at the central separator — the whole string is a palindrome. Manacher is the palindrome twin of the Z-algorithm: both cache a rightmost matched window and mirror earlier results into it, comparing fresh characters only past the edge. Same linear-time idea, different question — prefix matches there, palindrome radii here.
Check yourself
1 · Why insert # separators before running Manacher?
Separators turn even-length palindromes (centered between chars) into odd ones, so a single center-and-radius method handles both, and the radius maps to the original length.
2 · Inside the [C, R] window, how is P[i] first set?
The mirror position 2C − i already has a radius; you reuse it but cannot trust anything past R, so you cap at R − i, then expand.
3 · Why is the whole algorithm O(n)?
Reuse handles most positions with no comparisons; the only fresh comparisons advance R, which can move forward at most n times total.
Questions
Manacher vs expand-around-center?
Expand-around-center tries all ~2n centers and expands each independently, giving O(n²). Manacher keeps the same expansion but reuses the mirror radius inside the rightmost palindrome, so most centers start from a known radius and only genuine new matches cost work — O(n) overall.
How does it relate to the Z-algorithm and KMP?
All three are linear-time string tools built on a cached window and a mirror or failure function. The Z-algorithm measures prefix-match lengths, KMP tracks the longest prefix that is also a suffix, and Manacher measures palindrome radii. The window-reuse idea is shared.
How do I get the actual substring back?
In the padded string, P[i] is exactly the palindrome length in the original, and it starts at index (i − P[i]) / 2. Take the center with the largest P[i] and slice the original there.
The palindrome twin of the Z-algorithm.
Pad with separators, mirror the radii the window already knows, expand only past its edge — the longest palindrome falls out in one linear pass.