Palindrome algorithms — Manacher's algorithm: Visual walkthrough

We are answering one question the whole way down:

"At each spot in a string, how far does the palindrome around it reach — without re-checking ground we already checked?"

Step 1 — What is a palindrome, drawn as a mirror

WHAT. A palindrome is a string that reads the same forwards and backwards: racecar, abba, b. Pick a center and the string is a mirror image of itself around that center.

WHY we care about the center. Every palindrome has a middle. If we know, for each possible middle, how far the mirroring reaches, we know every palindrome in the string. So the whole problem becomes: for each center, find the radius.

PICTURE. Below, abcba is drawn with its center on the c. The green arrows show that position $c - 1$ equals $c + 1$ , and $c - 2$ equals $c + 2$ . The radius is how many matched pairs we get before the mirror breaks — here it is $2$ .

Figure — Palindrome algorithms — Manacher's algorithm

There are two annoying flavours: odd palindromes (aba, center is a letter) and even ones (abba, center is the gap between two letters). We fix this next.

Step 2 — The `#` trick: make every palindrome odd

WHAT. Insert a spacer # between every character and at both ends. abba becomes #a#b#b#a#. We call this new string $t$ .

WHY. An even palindrome has its center between two characters — there is no single index to stand on. After padding, that "between" gap is now occupied by a real #. So every palindrome in $t$ is centered on an actual index of $t$ , and every one has odd length. One uniform case instead of two.

PICTURE. The top row is abba. The bottom row is $t =$ #a#b#b#a#. The old even center (the gap between the two bs) is now the highlighted # at index $4$ — a real position we can stand on.

Related tools that solve the "find longest palindrome" task more slowly live at Longest Palindromic Substring and Expand Around Center — we are about to beat both.

Step 3 — The slow way, and exactly why it hurts

WHAT. Naive method: stand at each center $i$ , and expand outward one step at a time, comparing $t [i - k]$ with $t [i + k]$ until they differ. That is Expand Around Center.

WHY it's correct but slow. It is obviously correct. But look at aaaa. Every center can expand almost across the whole string, so we do roughly $\frac{m}{2}$ comparisons at $\frac{m}{2}$ centers → about $\frac{m ^{2}}{4}$ work. That is $O (n^{2})$ .

PICTURE. The red brackets show the expansion at three different centers of aaaa#-style input. Notice the massive overlap — the same characters get compared again and again. That wasted re-comparison is the enemy we will now eliminate.

Step 4 — The rightmost palindrome: the memory we carry

WHAT. As we sweep $i$ from left to right, we remember the single palindrome found so far that reaches furthest right. We store it as two numbers:

== $C$ == — its center index in $t$ .

== $R$ == — the index just past its right edge (its right boundary).

WHY these two. A palindrome centered at $C$ with right edge $R$ reaches $R - C$ steps each way, so it covers the interval $[2 C - R, R]$ . Knowing $(C, R)$ tells us exactly which region of $t$ is "already understood by symmetry." Everything about the trick happens inside this region.

PICTURE. The blue palindrome sits on the number line. $C$ is its center, $R$ its right wall, and $2 C - R$ its left wall (found by reflecting $R$ across $C$ ). The shaded band is our "known-mirror zone."

Step 5 — The mirror copy, and the wall that limits it

WHAT. Suppose our new center $i$ lies inside the blue palindrome, i.e. $i < R$ . Its mirror buddy is $i^{'} = 2 C - i$ , which we already visited (it is to the left). We tentatively set $P [i] = P [i^{'}]$ .

WHY. Inside the blue palindrome, position $i$ and position $i^{'}$ are mirror images. Whatever palindrome exists at $i^{'}$ is reflected to $i$ — as long as that reflected palindrome stays inside the blue walls. But if $P [i^{'}]$ is so big that the mirrored palindrome would poke past $R$ , we have no guarantee out there: symmetry only promises what is inside the blue region. So we must cap the copy at the distance to the wall, which is $R - i$ .

PICTURE. Two scenarios side by side.

Left (Case A): the buddy's palindrome (yellow) fits strictly inside the blue walls. Its mirror at $i$ (also yellow) is an exact, complete copy. $P [i] = P [i^{'}]$ , and no expansion is possible.

Right (Case B): the buddy's palindrome runs into (or past) the left wall $2 C - R$ . Its mirror at $i$ is only guaranteed up to the right wall $R$ . Beyond $R$ we are blind, so we cap at $R - i$ and must try to expand.

Step 6 — Expand past the wall (only when needed)

WHAT. After the mirror copy, we try to push further: while the characters just outside our current radius still match — $t [i - P [i] - 1] = t [i + P [i] + 1]$ — increase $P [i]$ by one.

WHY only sometimes. In Case A the copy is already maximal; the very first comparison fails, so the loop does zero work. In Case B we genuinely might extend past $R$ into unknown territory — that is the only place real comparisons happen. Then, if our new right edge $i + P [i]$ passes the old $R$ , we have found a new rightmost palindrome, so we update $C = i$ , $R = i + P [i]$ .

PICTURE. A Case-B center. The yellow part (up to the wall) came free from the mirror. The green part is the new expansion past $R$ , discovered by real comparisons. The red wall $R$ then jumps rightward to the new edge.

Step 7 — Why the total work is $O (n)$ (amortized)

WHAT. Add up all the expansion comparisons across the entire run.

WHY it's linear. The mirror step is $O (1)$ per index — no loop. The only loop is the expand loop, and every successful comparison there moves $R$ one step to the right. $R$ starts at $0$ and never decreases, and it can reach at most $m$ . So across the whole algorithm, the expand loop runs at most $m$ successful steps total — not per index, total. Plus one failed comparison per center. Grand total $O (m) = O (n)$ .

PICTURE. $R$ 's value plotted against the sweep index $i$ . It is a monotone staircase climbing from $0$ to $m$ . The area of climbing = total expansion work = bounded by the height $m$ . This is the same accounting idea as in Amortized Analysis.

Step 8 — The degenerate cases, so nothing surprises you

WHAT. The corners that break naive code.

PICTURE. Four tiny strings — a, aa, abc, aaaa — each with its final $P$ array printed underneath, so you can see the pattern in every regime.

The one-picture summary

PICTURE. The whole algorithm on one canvas: the blue rightmost palindrome $(C, R)$ , a new center $i$ inside it, its mirror buddy $i^{'}$ , the free copy (yellow) capped at the wall, the paid expansion (green) past $R$ , and the wall jumping to its new spot. This single diagram is Manacher's algorithm.

Related structures that also enumerate palindromes: Palindromic Tree (Eertree). The mirror/reuse idea echoes the Z-Algorithm and the KMP failure function — all three amortize by carrying a "reach so far" boundary.

Recall Feynman: retell the whole walkthrough in plain words

We had a string and wanted, for every possible middle, how far the mirror reflection reaches. Even-length mirrors were annoying, so we sprinkled # spacers to make every mirror odd — one clean shape. Then we noticed: if a big mirror already covers our new spot, the left side of that big mirror was already measured, and by symmetry it equals the right side. So we just peek at the mirror buddy and copy its answer — for free — but only as far as the big mirror's wall reaches; past the wall we know nothing. Where the buddy's answer runs into the wall, we roll up our sleeves and measure by hand, one step at a time, pushing the wall forward. Because the wall only ever moves forward and can only travel the length of the string, all the hand-measuring in the whole run adds up to just one pass. Mirror when you can, push the wall when you must — linear time.

Recall Self-check

On s="abba" with t="#a#b#b#a#", what is $P [4]$ and why? ::: $P [4] = 4$ : center # at index 4, mirror gives 0 but we sit exactly on the wall, so we must expand — and we uncover the whole abba, radius/length $4$ . Why is the mirror step capped at $R - i$ ? ::: Symmetry only guarantees what lies inside the rightmost palindrome; past the wall $R$ we have no information, so we cannot copy beyond it. Why is total expansion $O (n)$ ? ::: Every successful expand comparison pushes $R$ one step right; $R$ never retreats and maxes at $m$ , so total expansions $\leq m$ .