Palindrome algorithms — Manacher's algorithm: Worked examples

Before the matrix, one reminder of the vocabulary so no symbol is unearned:

If any of those feels shaky, re-read the parent's derivation. This page assumes only those five.

The scenario matrix

Every input Manacher can face falls into one of these cells. Each worked example below is tagged with the cell(s) it exercises.

Cell	What makes it special	Why it's a distinct case
A. Odd champion	longest palindrome has odd length (`aba`)	center lands on a real char of $t$
B. Even champion	longest palindrome has even length (`abba`)	center lands on a `#` of $t$
C. All-same	`aaaa…`	mirror predicts almost everything; expansion fires rarely — the $O (n)$ stress test
D. No repeats	every char distinct (`abcd`)	every $P [i] \leq 1$ ; degenerate, nothing to reuse
E. Mirror strictly inside (Case A)	$P [i^{'}] < R - i$	copy exactly, do not expand
F. Mirror hits wall (Case B)	$P [i^{'}] \geq R - i$	copy the cap $R - i$ , must expand past $R$
G. $i \geq R$ (outside)	fresh center, no info	start from $0$ , expand from scratch
H. Boundary / single char	`""`, `"a"`	degenerate limits; bounds checks matter
I. Index mapping	recover start in $s$	the `//2` trap that silently corrupts output
J. Counting	total palindromic substrings	uses $⌈ P [i] /2 ⌉$ per center
K. Word-problem / exam twist	applied phrasing	proves you can use it, not just run it

The eight examples below hit all cells A–K.

Worked examples

Example 1 — Odd champion, outside-center start (Cells A, G)

Worked example

s = "aba" Find the longest palindrome and its center.

Forecast: guess $P$ at the middle b's position in $t$ , and the final answer, before reading.

$t =$ #a#b#a#, indices $0..6$ , so $m = 7$ .

$i = 0$ (#): $i \geq R (= 0)$ , so start $P = 0$ . Try expand: $i - 1 = - 1$ out of bounds → stop. $P [0] = 0$ . Why this step? Cell G — no palindrome sits to the left of the very first #.
$i = 1$ (a): $i \geq R$ , start $0$ . Expand: t[0]=# vs t[2]=# match → $P = 1$ ; next t[-1] out of bounds → stop. Update $C = 1, R = 2$ . Why? First real center; expansion from scratch (Cell G) finds the single a.
$i = 2$ (#): $i < R$ . Mirror $i^{'} = 2 C - i = 0$ , $P [0] = 0$ , cap $R - i = 0$ → init $0$ . Expand: t[1]=a vs t[3]=b — no match. $P [2] = 0$ .
$i = 3$ (b): $i \geq R$ (since $R = 2$ ), start $0$ . Expand: t[2]=#=t[4]=# → $P = 1$ ; t[1]=a=t[5]=a → $P = 2$ ; t[0]=#=t[6]=# → $P = 3$ ; t[-1] out → stop. Update $C = 3, R = 6$ . Why? This is the champion: an odd palindrome aba centered on a real char (Cell A). $P = 3$ = length in $s$ .
$i = 4, 5, 6$ : all inside the big palindrome, mirrors give $P [4] = P [2] = 0$ , $P [5] = P [1] = 1$ , $P [6] = 0$ .

Answer: $max P = 3$ at $t$ -index $3$ → longest palindrome aba, length $3$ .

Verify: start in $s$ = $(k - P [k]) //2 = (3 - 3) //2 = 0$ ; s[0:0+3] = "aba". ✓ Length matches, center is a real char (odd) as predicted.

Example 2 — Even champion, mirror hits the wall (Cells B, F)

Worked example

s = "cbbc" Same shape as abba, but let's isolate Cell F (mirror exactly at wall) explicitly.

Forecast: which single $i$ forces a real expansion, and how far?

$t =$ #c#b#b#c#, $0..8$ , $m = 9$ .

$i = 1$ (c): expand → #=# → $P = 1$ , edge → stop. $C = 1, R = 2$ .
$i = 2$ (#): mirror $0$ , cap $0$ → $0$ ; t[1]=c vs t[3]=b mismatch → $P = 0$ .
$i = 3$ (b): $i \geq R$ , expand → #=# → $P = 1$ . $C = 3, R = 4$ .
$i = 4$ (#): mirror $i^{'} = 2$ , $P [2] = 0$ , cap $R - i = 0$ . Init $0$ . But $i = 4$ sits at $R$ 's influence edge → Cell F: must expand. t[3]=b=t[5]=b → $P = 1$ ; t[2]=#=t[6]=# → $P = 2$ ; t[1]=c=t[7]=c → $P = 3$ ; t[0]=#=t[8]=# → $P = 4$ ; edge → stop. Update $C = 4, R = 8$ . Why this step? The mirror predicted only $0$ , but because we were at the wall we had no right to stop — expansion revealed the whole even palindrome cbbc. Center on a # ⇒ even length (Cell B).
$i = 5$ (b): mirror $i^{'} = 3$ , $P [3] = 1$ ; cap $R - i = 8 - 5 = 3$ . $min (1, 3) = 1$ → Cell E (strictly inside): copy $1$ , no expand.

Answer: $max P = 4$ at $t$ -index $4$ → cbbc, even length $4$ .

Verify: start $= (4 - 4) //2 = 0$ ; s[0:4]="cbbc". ✓ Even palindrome centered on #.

Example 3 — Mirror strictly inside: the speedup you can watch (Cell E)

Worked example

s = "aca" inside a bigger frame: use s = "xacax" Isolate Cell E: a center whose mirror lives fully inside, so we copy and skip expansion.

Forecast: at the second a, will Manacher expand or just copy?

$t =$ #x#a#c#a#x#, indices $0..10$ , $m = 11$ .

Centers up to c (index $5$ ): expansion finds xacax is a full palindrome. At $i = 5$ (c), $P = 5$ (spans xacax). Update $C = 5, R = 10$ .
$i = 7$ (a): $i < R$ . Mirror $i^{'} = 2 \cdot 5 - 7 = 3$ , and $P [3]$ (the first a) $= 1$ . Cap $R - i = 10 - 7 = 3$ . $min (1, 3) = 1$ . Why? $P [i^{'}] = 1 < R - i = 3$ → Cell E: the mirror palindrome fits strictly inside the big one. Symmetry forces $P [7] = 1$ exactly. We do not run the expand loop meaningfully — the first comparison (t[5]=c vs t[9]=#? no: t[7-2]=t[5]=c vs t[7+2]=t[9]=x) mismatches immediately.

Answer: $P [7] = 1$ ; the champion stays $P [5] = 5$ → xacax.

Verify: start $= (5 - 5) //2 = 0$ ; s[0:5]="xacax". ✓ And $P [7] = 1$ copied, zero expansion work — the amortized savings in one frame (Cell E confirmed).

Example 4 — All-same: the $O (n)$ stress test (Cell C)

Worked example

s = "aaaa" The classic worst case for naive expand-around-center. Show that Manacher's total expansion is linear.

Forecast: how many times does the expand loop increment across the whole run? (Not per index — total.)

$t =$ #a#a#a#a#, $0..8$ , $m = 9$ .

The key claim: an increment happens only when it pushes $R$ rightward, and $R$ climbs $0 \to 8$ monotonically. So total increments $\leq m = 9$ .

Each real-char and each # center inherits most of its $P$ from its mirror (Cell E-style copies).
The expand loop only truly works at the centers that extend the wall — the red staircase in the figure shows $R$ never retreating.

Answer: $max P = 4$ at the middle # (index $4$ ) → aaaa, and total expansion increments across all $i$ is $\leq m$ .

Verify: In VERIFY we count actual increments for "aaaa" and confirm the total is $\leq 2 m$ (linear), plus $max P = 4$ . ✓ This is Amortized Analysis in action.

Example 5 — No repeats: everything degenerate (Cell D, H)

Example 6 — Index mapping: the `//2` trap (Cell I)

Worked example

s = "forgeeksskeegfor" The champion is geeksskeeg (length $10$ , even). We must recover its start index in $s$ correctly.

Forecast: the champion's center in $t$ is at some index $k$ with $P [k] = 10$ . Guess the start in $s$ before computing.

Run Manacher. The center of geeksskeeg sits on the # between the two middle s's. Suppose that $t$ -index is $k$ with $P [k] = 10$ . Why even? geeksskeeg has even length → center on a # (Cell B).
Map back: $start = (k - P [k]) //2$ . Why $//2$ ? $t$ is twice as dense as $s$ (a # between every pair). A span of $P [k]$ real chars starting at $t$ -index $k - P [k]$ corresponds to $s$ -index $(k - P [k]) /2$ . Forgetting the $//2$ points at a #, returning garbage.

Answer: longest_pal("forgeeksskeegfor") == "geeksskeeg", start index in $s$ is $3$ .

Verify: In VERIFY we compute both the substring and the start index. ✓

Example 7 — Counting all palindromic substrings (Cell J)

Example 8 — Word problem / exam twist (Cell K)

Recall Which cell does each trap live in?

Even champion centers on a # — which cell? ::: Cell B "Copy the mirror, skip expansion" — which cell? ::: Cell E (mirror strictly inside) "Mirror predicts too little, must expand past the wall" — which cell? ::: Cell F The //2 when mapping back to s — which cell? ::: Cell I aaaa… stress-testing linearity — which cell? ::: Cell C

See also: Expand Around Center (the $O (n^{2})$ baseline Manacher beats), Longest Palindromic Substring (the headline application), Palindromic Tree (Eertree) (an alternative structure), and the amortized-cost argument in Amortized Analysis.