Palindrome algorithms — Manacher's algorithm: Exercises

This page is a self-testing ladder. Each rung climbs one cognitive level, from recognising what the pieces mean up to mastering the amortized argument. Every problem has a full worked solution hidden inside a collapsible callout — try first, then reveal.

Prerequisites live in the parent note Manacher's algorithm and neighbours Expand Around Center, Longest Palindromic Substring, Amortized Analysis, Z-Algorithm, KMP failure function, and Palindromic Tree (Eertree).

Level 1 — Recognition

L1.1 — Build the transform

Problem. Write the transformed string $t$ for $s = aba$ . What is its length $m$ ? Which formula gives $m$ from $n = ∣ s ∣$ ?

Recall Solution

Insert # at every gap and both ends: $aba \to #a#b#a#$ That string has 7 characters. In general $m = 2 n + 1$ . Here $n = 3$ , so $m = 2 (3) + 1 = 7$ . ✓ Why $2 n + 1$ ? There are $n$ real characters and $n + 1$ gaps (before, between, after), giving $n + (n + 1) = 2 n + 1$ separators-plus-reals.

L1.2 — Read a $P$ value

Problem. In $t = #a#b#a#$ (indices $0 \dots 6$ ), the center $i = 3$ sits on the b. By hand, $P [3] = 3$ . What palindrome in the original $s$ does this describe, and how long is it?

Recall Solution

Radius $3$ around index $3$ spans indices $0 \dots 6$ , i.e. the whole #a#b#a#. Removing the spacers gives aba. The recovery rule says the original palindrome length equals $P [i]$ directly, so length $= 3$ . The substring is ==aba==. ✓

Level 2 — Application

L2.1 — Full trace on `s = "aba"`

Problem. Run Manacher on $t = #a#b#a#$ . Fill the table: for each $i$ , give the mirror $i^{'} = 2 C - i$ (if $i < R$ ), the initial $P [i]$ , the value after expansion, and any $(C, R)$ update.

Recall Solution

Start $C = R = 0$ .

$i$	$t [i]$	$i^{'} = 2 C - i$	init $P [i]$	after expand	update
0	#	— ( $i \geq R$ )	0	0	—
1	a	— ( $i \geq R$ )	0	1 (`t[0]=#=t[2]=#`)	$C = 1, R = 2$
2	#	$i^{'} = 0$ , $P = 0$	$min (0, R - i = 0) = 0$	0	—
3	b	— ( $i \geq R$ , since $R = 2$ )	0	3 (`b`, then `#=#`... `a=a`... `#=#`)	$C = 3, R = 6$
4	#	$i^{'} = 2$ , $P = 0$	$min (0, 2) = 0$	0	—
5	a	$i^{'} = 1$ , $P = 1$	$min (1, 1) = 1$	1	—
6	#	$i^{'} = 0$ , $P = 0$	$min (0, 0) = 0$	0	—

Final $P = [0, 1, 0, 3, 0, 1, 0]$ . $max P = 3$ at $i = 3$ → longest palindrome aba, length 3. ✓ Why no expansion at $i = 5$ ? Mirror $i^{'} = 1$ had $P = 1$ , and $P [i^{'}] = 1 = R - i = 1$ (equals the wall). We take $min = 1$ ; the value touches the wall so in principle we try to expand — but t[7] is out of bounds, so nothing changes. This is Case B degenerating harmlessly at the string edge.

L2.2 — Recover the substring index

Problem. For s = "abacabad", suppose the maximum radius is $P [k] = 5$ at $t$ -index $k = 7$ . Give the starting index in $s$ and the substring length.

Recall Solution

The mapping rule: start = (k - P[k]) // 2. $start = \frac{7 - 5}{2} = \frac{2}{2} = 1.$ Length $= P [k] = 5$ . So the substring is s[1:6]. For s = "abacabad", s[1:6] = "bacab", which is a palindrome of length 5. ✓ Why the $//2$ ? $t$ is twice as dense as $s$ (every real char has a # neighbour). A left edge at $t$ -index $k - P [k]$ corresponds to an $s$ -index of half that — and because $t$ starts with #, integer division lands exactly.

Level 3 — Analysis

L3.1 — Counting all palindromic substrings

Problem. Using the fact that the number of palindromic substrings centered at $t [i]$ is $⌈ P [i] /2 ⌉$ , count the total number of palindromic substrings of s = "aaa".

Recall Solution

$t = #a#a#a#$ , indices $0 \dots 6$ . Compute $P$ (you can verify by symmetry): $P = [0, 1, 0, 3, 0, 1, 0]$ ... wait, aaa fully palindromic. Let's run it:

$i = 1$ (a): expands to $P = 1$ , set $C = 1, R = 2$ .
$i = 2$ (#): mirror $i^{'} = 0, P = 0$ ; init $min (0, 0) = 0$ ; expand t[1]=a=t[3]=a → $P = 1$ ; then t[0]=#=t[4]=# → $P = 2$ ; set $C = 2, R = 4$ .
$i = 3$ (a): mirror $i^{'} = 1, P = 1$ ; init $min (1, R - i = 1) = 1$ ; expand t[2]=#=t[4]=# → 2, t[1]=a=t[5]=a → 3, t[0]=#=t[6]=# → wait bounds: t[0] and t[6] → 3; set $C = 3, R = 6$ .
$i = 4$ (#): mirror $i^{'} = 2, P = 2$ ; init $min (2, R - i = 2) = 2$ ; can't expand past bounds → 2.
$i = 5$ (a): mirror $i^{'} = 1, P = 1$ ; init $min (1, 1) = 1$ → 1.
$i = 6$ (#): 0.

So $P = [0, 1, 2, 3, 2, 1, 0]$ . Now sum $⌈ P [i] /2 ⌉$ : $0 + 1 + 1 + 2 + 1 + 1 + 0 = 6.$ The 6 palindromic substrings of aaa: three single a, two aa, one aaa → $3 + 2 + 1 = 6$ . ✓ Total = 6.

L3.2 — Why $min$ and not just the mirror

Problem. Give a concrete $t$ and index $i$ where blindly setting P[i] = P[2C-i] (no cap) would claim a palindrome that does not exist. Explain in one sentence why the cap fixes it.

Recall Solution

Take $t = #a#b#a#c#a#b#a#$ — no, simpler. Consider the classic $t$ from abacaba-style where a mirror palindrome pokes out. A minimal example: $t = #b#a#a#b#$ (from s="baab"). Suppose $C = 4$ (# at middle), $R = 8$ , and we reach $i = 5$ . Mirror $i^{'} = 2 C - i = 3$ . If $P [3] = 1$ but $R - i = 3$ , that's Case A (fits) — not the poke-out case. The poke-out happens when $P [i^{'}] > R - i$ : the mirror palindrome extends left past the big palindrome's left edge $2 C - R$ . Beyond that edge there is no symmetry guarantee, so copying $P [i^{'}]$ asserts matching characters we never verified. One sentence: capping at $R - i$ trusts symmetry only up to the wall $R$ , then earns any extra by actually comparing characters. ✓

Level 4 — Synthesis

L4.1 — Amortized bound, from scratch

Problem. Prove that the total number of character comparisons in all expand loops across a full run is at most $m$ (the length of $t$ ). Reference the figure for the mechanism.

Figure — Palindrome algorithms — Manacher's algorithm

Recall Solution

Split each iteration's work into two buckets:

The min step is $O (1)$ : pure arithmetic, no comparisons. Ignore it.
The expand loop does one character comparison per iteration. Here is the key: after the initial min, the palindrome at $i$ already reaches up to $R$ (the wall). Every successful comparison inside the expand loop pushes the palindrome's right edge to $i + P [i] > R$ , and then we execute R = i + P[i].

Look at the figure: the red wall marker $R$ only ever slides right, never left. Each successful expand comparison advances $R$ by exactly one position (in $t$ ). Since $R$ starts at $0$ and can never exceed $m$ , the number of successful comparisons over the whole run is $\leq m$ .

Each expand loop ends with at most one failing comparison (the mismatch that stops it), and there are $m$ centers, giving $\leq m$ failing comparisons. Total comparisons $\leq m + m = 2 m = O (m) = O (n)$ . ✓ This is the Amortized Analysis argument: individual centers may expand a lot, but the shared resource $R$ can only move forward $m$ steps total.

L4.2 — Design a worst case for naive expand

Problem. Expand Around Center runs in $Θ (n^{2})$ on some inputs. Construct a family of strings of length $n$ that forces this, and compute the exact number of successful expand comparisons for $s = aaaa$ ( $n = 4$ ) under the naive (no-mirror) algorithm.

Recall Solution

The worst case is the all-same string $s = a^{n}$ . Every center is the middle of a large palindrome, so expansion runs far from each center. Count successful comparisons for aaaa on $t = #a#a#a#a#$ (indices $0..8$ ), where naive expand tries every center independently: By symmetry the radii are $P = [0, 1, 2, 3, 4, 3, 2, 1, 0]$ (the middle # at $i = 4$ centers the whole aaaa). Sum of radii = number of successful comparisons under naive expand (each expansion is one success): $0 + 1 + 2 + 3 + 4 + 3 + 2 + 1 + 0 = 16.$ So naive does 16 successful comparisons for $n = 4$ . In general $\sum P [i] \approx \frac{n ^{2}}{2}$ → $Θ (n^{2})$ . Manacher, by contrast, keeps total expansion bounded by $m$ because it reuses mirror values. ✓

Level 5 — Mastery

L5.1 — Relate to Z-Algorithm reflection

Problem. Both Manacher and the Z-Algorithm maintain a rightmost window $[L, R]$ and reuse previously computed values via reflection. State the analogous recurrence in the Z-algorithm and name the one structural difference in what gets reflected.

Recall Solution

In the Z-algorithm we maintain a window $[L, R]$ = the rightmost segment matching a prefix. For position $i$ inside it, the mirror is $i - L$ (offset from the window's left start), and: $Z [i] = min (Z [i - L], R - i + 1), then extend.$ Compare Manacher: $P [i] = min (P [2 C - i], R - i)$ , then expand. The structural difference: Manacher reflects across a center $C$ (mirror index $2 C - i$ , a point reflection), because palindromes are symmetric about a point. The Z-algorithm reflects to the window's start $L$ (translation to $i - L$ ), because prefix-matches are compared against a fixed prefix, not a mirror. Both are the same amortized idea: trust the reused value up to the wall $R$ , then earn the rest. Related failure-function machinery appears in KMP failure function and the palindrome-specific automaton in Palindromic Tree (Eertree). ✓

L5.2 — Longest palindromic substring, end to end

Problem. For s = "forgeeksskeegfor", apply the full pipeline: what is the longest palindromic substring and its length? Show which $k$ and $P [k]$ produce it, and verify the start-index mapping.

Recall Solution

The obvious long palindrome is geeksskeeg (length 10). Let's confirm via the pipeline. In $t$ , this palindrome is even-length in $s$ , so its center in $t$ is a #. Its radius in $t$ equals its original length, so $P [k] = 10$ at that center. The palindrome geeksskeeg starts at $s$ -index 3 (f o r g..., g is index 3). Mapping: start = (k - P[k]) // 2. We need (k - 10)//2 = 3, so $k - 10 = 6$ , i.e. $k = 16$ . That $t$ -index is the # between the two s characters — the true even center. ✓ Final answer: longest palindromic substring = ==geeksskeeg, length 10==. This matches Longest Palindromic Substring via s[start:start+P[k]] = s[3:13]. ✓

Recall Self-check: five one-line reveals

P[i] equals what, in the original string? ::: The exact length of the palindrome centered at t[i] in s. Why min(P[2C-i], R-i) instead of just P[2C-i]? ::: Because symmetry is only guaranteed up to the wall R; past it we must verify. What single quantity makes the algorithm O(n)? ::: The wall R only moves rightward, at most m steps in total. Map t-index k with radius P[k] to an s start-index. ::: start = (k - P[k]) // 2. Why insert # separators? ::: They make every palindrome odd-length so only one case is handled.