Palindrome algorithms — Manacher's algorithm: Worked examples

3.8.9 · D3 · Coding › String Algorithms › Palindrome algorithms — Manacher's algorithm

Matrix se pehle, vocabulary ka ek reminder taaki koi symbol anjaana na lage:

Agar inme se koi shaky lage, toh parent ki derivation dobara padho. Yeh page sirf unhi paanch cheezon ko assume karta hai.

Scenario matrix

Har input jo Manacher face kar sakta hai, inhi cells mein se ek mein aata hai. Neeche har worked example tagged hai un cell(s) ke saath jo woh exercise karta hai.

Cell	Kya khaas hai	Yeh alag case kyun hai
A. Odd champion	longest palindrome ki odd length hai (`aba`)	center $t$ ke ek real char pe padta hai
B. Even champion	longest palindrome ki even length hai (`abba`)	center $t$ ke ek `#` pe padta hai
C. All-same	`aaaa…`	mirror almost sab kuch predict karta hai; expansion rarely fire hoti hai — $O (n)$ stress test
D. No repeats	har char alag (`abcd`)	har $P [i] \leq 1$ ; degenerate, reuse karne ko kuch nahi
E. Mirror strictly inside (Case A)	$P [i^{'}] < R - i$	exactly copy karo, expand mat karo
F. Mirror hits wall (Case B)	$P [i^{'}] \geq R - i$	cap $R - i$ copy karo, $R$ ke aage expand karna zaroori hai
G. $i \geq R$ (outside)	fresh center, koi info nahi	$0$ se shuru karo, scratch se expand karo
H. Boundary / single char	`""`, `"a"`	degenerate limits; bounds checks matter karte hain
I. Index mapping	$s$ mein start recover karo	`//2` ka trap jo silently output corrupt karta hai
J. Counting	total palindromic substrings	har center pe $⌈ P [i] /2 ⌉$ use karta hai
K. Word-problem / exam twist	applied phrasing	prove karta hai ki tum ise use kar sakte ho, sirf run nahi

Neeche ke aath examples saare cells A–K hit karte hain.

Worked examples

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

Worked example

s = "aba" Longest palindrome aur uska center dhundho.

Forecast: $t$ mein beech wale b ki position pe $P$ guess karo, aur final answer, padhne se pehle.

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

$i = 0$ (#): $i \geq R (= 0)$ , toh $P = 0$ se shuru karo. Expand try karo: $i - 1 = - 1$ out of bounds → ruko. $P [0] = 0$ . Yeh step kyun? Cell G — pehle # ke bilkul left mein koi palindrome nahi baith sakta.
$i = 1$ (a): $i \geq R$ , $0$ se shuru karo. Expand: t[0]=# vs t[2]=# match → $P = 1$ ; next t[-1] out of bounds → ruko. Update $C = 1, R = 2$ . Kyun? Pehla real center; scratch se expansion (Cell G) single a dhundh leta hai.
$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 — match nahi. $P [2] = 0$ .
$i = 3$ (b): $i \geq R$ (kyunki $R = 2$ ), $0$ se shuru karo. Expand: t[2]=#=t[4]=# → $P = 1$ ; t[1]=a=t[5]=a → $P = 2$ ; t[0]=#=t[6]=# → $P = 3$ ; t[-1] out → ruko. Update $C = 3, R = 6$ . Kyun? Yeh champion hai: ek odd palindrome aba ek real char pe centered (Cell A). $P = 3$ = $s$ mein length.
$i = 4, 5, 6$ : sab bade palindrome ke andar, mirrors dete hain $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 match karti hai, center ek real char hai (odd) jaisa predict kiya tha.

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

Worked example

s = "cbbc" abba jaisi hi shape, lekin Cell F (mirror exactly at wall) ko explicitly isolate karte hain.

Forecast: kaun sa single $i$ ek real expansion force karta hai, aur kitni door?

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

$i = 1$ (c): expand → #=# → $P = 1$ , edge → ruko. $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$ . Lekin $i = 4$ $R$ ke influence edge pe baithta hai → Cell F: expand karna zaroori hai. 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 → ruko. Update $C = 4, R = 8$ . Yeh step kyun? Mirror sirf $0$ predict kar raha tha, lekin kyunki hum wall pe the isliye rukne ka koi haq nahi tha — expansion ne poore even palindrome cbbc ko reveal kiya. # pe center ⇒ 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): $1$ copy karo, expand mat karo.

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

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

Example 3 — Mirror strictly inside: woh speedup jo tum dekh sakte ho (Cell E)

Worked example

s = "aca" ek bade frame ke andar: use karo s = "xacax" Cell E isolate karo: ek center jiska mirror fully andar rehta hai, toh hum copy karte hain aur expansion skip karte hain.

Forecast: doosre a pe, kya Manacher expand karega ya sirf copy karega?

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

c (index $5$ ) tak ke centers: expansion dhundh leta hai ki xacax ek full palindrome hai. $i = 5$ pe (c), $P = 5$ (xacax span karta hai). Update $C = 5, R = 10$ .
$i = 7$ (a): $i < R$ . Mirror $i^{'} = 2 \cdot 5 - 7 = 3$ , aur $P [3]$ (pehla a) $= 1$ . Cap $R - i = 10 - 7 = 3$ . $min (1, 3) = 1$ . Kyun? $P [i^{'}] = 1 < R - i = 3$ → Cell E: mirror palindrome bade wale ke andar strictly fit hota hai. Symmetry force karti hai ki $P [7] = 1$ exactly ho. Hum expand loop meaningfully nahi chalate — pehla comparison (t[5]=c vs t[9]=#? nahi: t[7-2]=t[5]=c vs t[7+2]=t[9]=x) immediately mismatch karta hai.

Answer: $P [7] = 1$ ; champion $P [5] = 5$ rehta hai → xacax.

Verify: start $= (5 - 5) //2 = 0$ ; s[0:5]="xacax". ✓ Aur $P [7] = 1$ copy kiya gaya, zero expansion work — ek frame mein amortized savings (Cell E confirmed).

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

Worked example

s = "aaaa" Naive expand-around-center ke liye classic worst case. Dikhao ki Manacher ki total expansion linear hai.

Forecast: poore run mein expand loop kitni baar increment karta hai? (Per index nahi — total.)

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

Key claim: ek increment tabhi hota hai jab woh $R$ ko rightward push karta hai, aur $R$ monotonically $0 \to 8$ climb karta hai. Toh total increments $\leq m = 9$ .

Har real-char aur har # center apna zyaada $P$ apne mirror se inherit karta hai (Cell E-style copies).
Expand loop sirf un centers pe sach mein kaam karta hai jo wall ko extend karte hain — figure mein red staircase dikhata hai ki $R$ kabhi retreat nahi karta.

Answer: $max P = 4$ beech wale # pe (index $4$ ) → aaaa, aur saare $i$ ke across total expansion increments $\leq m$ hain.

Verify: VERIFY mein hum "aaaa" ke liye actual increments count karte hain aur confirm karte hain ki total $\leq 2 m$ (linear) hai, plus $max P = 4$ . ✓ Yeh Amortized Analysis in action hai.

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

Worked example

s = "abcd" Har character alag — single letter se zyada koi palindrome nahi.

Forecast: $max P$ kya hai? Woh champion ke baare mein kya kehta hai?

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

Har real-char center apne do # neighbours pe ek baar expand karta hai? Chaliye i=1 (a) check karte hain: t[0]=#=t[2]=# → $P = 1$ ; t[-1] out → ruko. Toh $P = 1$ . Kyun? Ek akela letter ek length $1$ ka palindrome hai; uske around #-# hamesha match karte hain, $P = 1$ dete hain, kabhi zyada nahi, kyunki real neighbours alag hain.
Har # center: neighbours do alag real chars hain → immediately mismatch → $P = 0$ .

Answer: $max P = 1$ → longest palindrome koi bhi single character hai, length $1$ (Cell D). Matrix ki koi cell skip nahi hui: yeh "reuse karne ko kuch nahi" degenerate limit hai.

Verify: max(manacher("abcd")) == 1. ✓

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

Worked example

s = "forgeeksskeegfor" Champion geeksskeeg hai (length $10$ , even). Hume $s$ mein iska start index correctly recover karna hai.

Forecast: champion ka center $t$ mein kisi index $k$ pe hai jahan $P [k] = 10$ hai. $s$ mein start compute karne se pehle guess karo.

Manacher run karo. geeksskeeg ka center do beech wale s's ke beech wale # pe baithta hai. Maano woh $t$ -index $k$ hai jahan $P [k] = 10$ hai. Even kyun? geeksskeeg ki even length hai → # pe center (Cell B).
Map back: $start = (k - P [k]) //2$ . $//2$ kyun? $t$ $s$ se do guna dense hai (har pair ke beech ek #). $t$ -index $k - P [k]$ se shuru hoke $P [k]$ real chars ka span $s$ -index $(k - P [k]) /2$ correspond karta hai. $//2$ bhoolne se ek # pe point karta hai, garbage return karta hai.

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

Verify: VERIFY mein hum dono substring aur start index compute karte hain. ✓

Example 7 — Saare palindromic substrings count karna (Cell J)

Worked example

s = "aaa" Har ek palindromic substring count karo (a×3, aa×2, aaa×1 = 6).

Forecast: $6$ guess kiya? Chaliye formula se deliver karwaate hain.

$t =$ #a#a#a#, $0..6$ , $m = 7$ . $P$ compute karo: beech wale a pe (index $3$ ) $P = 3$ ; do bahar wale a's ko $P = 1$ milta hai; do andar wale #'s ko $P = 2$ milta hai; bahar wale #'s ko $0$ .

Count per center $= ⌈ P [i] /2 ⌉$ :

real a at $i = 1$ : $⌈ 1/2 ⌉ = 1$
# at $i = 2$ : $⌈ 2/2 ⌉ = 1$
a at $i = 3$ : $⌈ 3/2 ⌉ = 2$
# at $i = 4$ : $⌈ 2/2 ⌉ = 1$
a at $i = 5$ : $⌈ 1/2 ⌉ = 1$

Sum $= 1 + 1 + 2 + 1 + 1 = 6$ . $⌈ P [i] /2 ⌉$ kyun? $t$ mein center $i$ ke around har odd-radius layer exactly ek real palindrome correspond karta hai; ceiling count karta hai ki us center pe kitne real-length palindromes nest hote hain.

Answer: $6$ palindromic substrings.

Verify: "aaa" ke saare substrings pe brute-force count Manacher formula sum ke barabar hai. ✓

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

Worked example DNA scanner

Ek lab ek DNA strand s = "atgcgta" read karta hai. Ek "hairpin loop" tab form hoti hai jab koi substring aage aur peechhe ek jaisi padhi jaaye. Longest hairpin aur uska start position report karo.

Forecast: eyeball karo — kya tum koi palindrome dekh rahe ho? Uski length guess karo.

$t =$ #a#t#g#c#g#t#a#. Manacher run karo. Manacher kyun, brute force kyun nahi? Ek genome millions of bases ka ho sakta hai; brute expand-around-center $Θ (n^{2})$ hai (repetitive DNA pe Cell C blow up ho jaata hai). Manacher $O (n)$ rehta hai.
Champion c pe centered hai (odd, Cell A): tgcgt? Check karo — atgcgta: reverse hai atgcgta… poori string ek palindrome hai! $max P = 7$ .

Answer: longest hairpin = atgcgta, length $7$ , start index $0$ .

Verify: longest_pal("atgcgta") == "atgcgta", max(manacher("atgcgta")) == 7. ✓

Recall Har trap kaun si cell mein rehta hai?

Even champion # pe center hota hai — kaun si cell? ::: Cell B "Mirror copy karo, expansion skip karo" — kaun si cell? ::: Cell E (mirror strictly inside) "Mirror bahut kam predict karta hai, wall ke aage expand karna zaroori hai" — kaun si cell? ::: Cell F s pe map back karte waqt //2 — kaun si cell? ::: Cell I aaaa… linearity stress-test — kaun si cell? ::: Cell C

Yeh bhi dekho: Expand Around Center ( $O (n^{2})$ baseline jo Manacher beat karta hai), Longest Palindromic Substring (headline application), Palindromic Tree (Eertree) (ek alternative structure), aur Amortized Analysis mein amortized-cost argument.