Palindrome algorithms — Manacher's algorithm: Exercises

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

Yeh page ek self-testing ladder hai. Har rung ek cognitive level upar chadhti hai — pieces ko pehchanne se lekar amortized argument ko master karne tak. Har problem ka ek pura worked solution ek collapsible callout ke andar chhupa hua hai — pehle khud try karo, phir reveal karo.

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

Intuition Shuru karne se pehle — woh vocabulary jo tumhari honi chahiye

Yahan sab kuch teen cheezein use karta hai. Har ek ko zor se bolo:

Transform $t$ : hum har character ke beech aur dono ends pe # insert karte hain, toh abba ban jaata hai #a#b#b#a#. Isse har palindrome odd-length ho jaata hai toh hum sirf ek case handle karte hain.
Radius array $P [i]$ : $t$ mein center $i$ ke har side pe kitne characters bahar nikalte hain. Khaas baat yeh hai ki $P [i]$ original string $s$ mein corresponding palindrome ki length ke barabar bhi hota hai.
Window $(C, R)$ : ab tak mila sabse door tak pahunchne wala palindrome ka center aur right-edge. $R$ ek "wall" hai — hum uske andar mirror par trust karte hain, aur usse aage kuch nahi jaante.

Ek-line engine: P[i] = min(P[2C-i], R-i) phir expand karo, phir shayad wall aage badhaao.

Level 1 — Recognition

L1.1 — Transform banao

Problem. $s = aba$ ke liye transformed string $t$ likho. Uski length $m$ kya hai? $n = ∣ s ∣$ se $m$ kaunsa formula deta hai?

Recall Solution

Har gap aur dono ends pe # insert karo: $aba \to #a#b#a#$ Us string mein 7 characters hain. Generally $m = 2 n + 1$ . Yahan $n = 3$ , toh $m = 2 (3) + 1 = 7$ . ✓ $2 n + 1$ kyun? $n$ real characters hain aur $n + 1$ gaps hain (pehle, beech mein, baad mein), jo deta hai $n + (n + 1) = 2 n + 1$ separators-plus-reals.

L1.2 — $P$ value padhna

Problem. $t = #a#b#a#$ (indices $0 \dots 6$ ) mein, center $i = 3$ b par baitha hai. Haath se, $P [3] = 3$ . Original $s$ mein yeh kaunsa palindrome describe karta hai, aur kitna lamba hai?

Recall Solution

Index $3$ ke around radius $3$ , indices $0 \dots 6$ tak phaila hua hai, yani poora #a#b#a#. Spacers hataane se milta hai aba. Recovery rule kehta hai ki original palindrome length directly $P [i]$ ke barabar hoti hai, toh length $= 3$ . Substring hai ==aba==. ✓

Level 2 — Application

L2.1 — `s = "aba"` par full trace

Problem. $t = #a#b#a#$ par Manacher run karo. Table bharo: har $i$ ke liye mirror $i^{'} = 2 C - i$ (agar $i < R$ ), initial $P [i]$ , expansion ke baad value, aur koi $(C, R)$ update do.

Recall Solution

$C = R = 0$ se start karo.

$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$ → sabse lamba palindrome aba, length 3. ✓ $i = 5$ par expansion kyun nahi? Mirror $i^{'} = 1$ ka $P = 1$ tha, aur $P [i^{'}] = 1 = R - i = 1$ (wall ke barabar). Hum $min = 1$ lete hain; value wall ko touch karti hai toh principle mein hum expand karne ki koshish karte hain — lekin t[7] bounds se bahar hai, toh kuch nahi badlta. Yeh Case B hai jo string edge par harmlessly degenerate ho jaata hai.

L2.2 — Substring index recover karna

Problem. s = "abacabad" ke liye, maano maximum radius $P [k] = 5$ hai $t$ -index $k = 7$ par. $s$ mein starting index aur substring length do.

Recall Solution

Mapping rule: start = (k - P[k]) // 2. $start = \frac{7 - 5}{2} = \frac{2}{2} = 1.$ Length $= P [k] = 5$ . Toh substring hai s[1:6]. s = "abacabad" ke liye, s[1:6] = "bacab", jo length 5 ka palindrome hai. ✓ $//2$ kyun? $t$ , $s$ se double dense hai (har real char ka ek # neighbour hai). $t$ -index $k - P [k]$ par left edge, $s$ -index ke aadhey ke corresponding hai — aur kyunki $t$ # se start hota hai, integer division exactly land karta hai.

Level 3 — Analysis

L3.1 — Sabhi palindromic substrings ginana

Problem. Is fact ka use karte hue ki $t [i]$ par centered palindromic substrings ki count $⌈ P [i] /2 ⌉$ hai, s = "aaa" ke palindromic substrings ki total count karo.

Recall Solution

$t = #a#a#a#$ , indices $0 \dots 6$ . $P$ compute karo (symmetry se verify kar sakte ho): $P = [0, 1, 0, 3, 0, 1, 0]$ ... ruko, aaa fully palindromic hai. Chalao:

$i = 1$ (a): $P = 1$ tak expand karta hai, $C = 1, R = 2$ set karo.
$i = 2$ (#): mirror $i^{'} = 0, P = 0$ ; init $min (0, 0) = 0$ ; expand t[1]=a=t[3]=a → $P = 1$ ; phir t[0]=#=t[4]=# → $P = 2$ ; $C = 2, R = 4$ set karo.
$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]=# → 3; $C = 3, R = 6$ set karo.
$i = 4$ (#): mirror $i^{'} = 2, P = 2$ ; init $min (2, R - i = 2) = 2$ ; bounds ke baad expand nahi ho sakta → 2.
$i = 5$ (a): mirror $i^{'} = 1, P = 1$ ; init $min (1, 1) = 1$ → 1.
$i = 6$ (#): 0.

Toh $P = [0, 1, 2, 3, 2, 1, 0]$ . Ab $⌈ P [i] /2 ⌉$ sum karo: $0 + 1 + 1 + 2 + 1 + 1 + 0 = 6.$ aaa ke 6 palindromic substrings: teen single a, do aa, ek aaa → $3 + 2 + 1 = 6$ . ✓ Total = 6.

L3.2 — $min$ kyun, aur sirf mirror kyun nahi

Problem. Ek concrete $t$ aur index $i$ do jahan blindly P[i] = P[2C-i] set karna (koi cap nahi) ek aisa palindrome claim karega jo actually exist nahi karta. Ek sentence mein explain karo ki cap kyun fix karta hai.

Recall Solution

$t = #b#a#a#b#$ lo (from s="baab"). Maano $C = 4$ (# at middle), $R = 8$ , aur hum $i = 5$ par pahunch rahe hain. Mirror $i^{'} = 2 C - i = 3$ . Agar $P [3] = 1$ lekin $R - i = 3$ , toh yeh Case A hai (fit hota hai) — yeh poke-out case nahi hai. Poke-out tab hota hai jab $P [i^{'}] > R - i$ : mirror palindrome badi palindrome ke left edge $2 C - R$ se left past extend karta hai. Us edge ke baad koi symmetry guarantee nahi hai, toh $P [i^{'}]$ copy karna aise characters ke matching ko assert karta hai jo humne kabhi verify nahi kiye. Ek sentence: $R - i$ par cap karna symmetry sirf wall $R$ tak trust karta hai, phir actually characters compare karke kuch bhi extra earn karta hai. ✓

Level 4 — Synthesis

L4.1 — Amortized bound, scratch se

Problem. Prove karo ki ek puri run mein sab expand loops mein character comparisons ki total count at most $m$ (yani $t$ ki length) hai. Figure mein mechanism reference karo.

Figure — Palindrome algorithms — Manacher's algorithm

Recall Solution

Har iteration ke kaam ko do buckets mein split karo:

min step $O (1)$ hai: pure arithmetic, koi comparisons nahi. Ignore karo.
Expand loop ek character comparison per iteration karta hai. Yahan key baat yeh hai: initial min ke baad, $i$ par palindrome already $R$ (wall) tak pahunch chuka hota hai. Expand loop ke andar har successful comparison palindrome ke right edge ko $i + P [i] > R$ tak push karta hai, aur phir hum R = i + P[i] execute karte hain.

Figure dekho: red wall marker $R$ sirf right slide karta hai, kabhi left nahi. Har successful expand comparison $R$ ko exactly ek position (in $t$ ) aage badhata hai. Kyunki $R$ $0$ se start hota hai aur $m$ se kabhi exceed nahi kar sakta, poori run mein successful comparisons ki count $\leq m$ hai.

Har expand loop at most ek failing comparison ke saath khatam hota hai (woh mismatch jo use rokta hai), aur $m$ centers hain, jo deta hai $\leq m$ failing comparisons. Total comparisons $\leq m + m = 2 m = O (m) = O (n)$ . ✓ Yeh Amortized Analysis argument hai: individual centers bahut zyada expand kar sakte hain, lekin shared resource $R$ sirf total $m$ steps aage ja sakta hai.

L4.2 — Naive expand ke liye worst case design karo

Problem. Expand Around Center kuch inputs par $Θ (n^{2})$ mein run karta hai. Length $n$ ki strings ki aisi family construct karo jo ise force kare, aur naive (no-mirror) algorithm ke under s = \texttt{aaaa} ( $n = 4$ ) ke liye successful expand comparisons ki exact count compute karo.

Recall Solution

Worst case hai all-same string $s = a^{n}$ . Har center ek badi palindrome ka middle hai, toh expansion har center se bahut door tak jaata hai. aaaa ke liye successful comparisons count karo $t = #a#a#a#a#$ (indices $0..8$ ) par, jahan naive expand har center ko independently try karta hai: Symmetry se radii hain $P = [0, 1, 2, 3, 4, 3, 2, 1, 0]$ ( $i = 4$ par middle # poore aaaa ko center karta hai). Radii ka sum = naive expand ke under successful comparisons ki count (har expansion ek success hai): $0 + 1 + 2 + 3 + 4 + 3 + 2 + 1 + 0 = 16.$ Toh naive $n = 4$ ke liye 16 successful comparisons karta hai. Generally $\sum P [i] \approx \frac{n ^{2}}{2}$ → $Θ (n^{2})$ . Manacher, iske contrast mein, mirror values reuse karke total expansion $m$ se bound rakhta hai. ✓

Level 5 — Mastery

L5.1 — Z-Algorithm reflection se relate karo

Problem. Manacher aur Z-Algorithm dono rightmost window $[L, R]$ maintain karte hain aur reflection ke zariye previously computed values reuse karte hain. Z-algorithm mein analogous recurrence state karo aur naam lo ek structural difference jo reflect hoti hai.

Recall Solution

Z-algorithm mein hum window $[L, R]$ maintain karte hain = ek prefix se match karne wala rightmost segment. Uske andar position $i$ ke liye, mirror $i - L$ hai (window ke left start se offset), aur: $Z [i] = min (Z [i - L], R - i + 1), phir extend karo.$ Compare Manacher: $P [i] = min (P [2 C - i], R - i)$ , phir expand karo. Structural difference: Manacher center $C$ ke around reflect karta hai (mirror index $2 C - i$ , ek point reflection), kyunki palindromes ek point ke baare mein symmetric hote hain. Z-algorithm window ke start $L$ tak reflect karta hai (translation to $i - L$ ), kyunki prefix-matches ek fixed prefix ke against compare hote hain, mirror nahi. Dono same amortized idea hain: reused value ko wall $R$ tak trust karo, phir baaki earn karo. Related failure-function machinery KMP failure function mein milti hai aur palindrome-specific automaton Palindromic Tree (Eertree) mein. ✓

L5.2 — Longest palindromic substring, end to end

Problem. s = "forgeeksskeegfor" ke liye, pura pipeline apply karo: sabse lamba palindromic substring kya hai aur uski length kya hai? Dikhao ki kaunsa $k$ aur $P [k]$ ise produce karta hai, aur start-index mapping verify karo.

Recall Solution

Obvious lamba palindrome hai geeksskeeg (length 10). Pipeline se confirm karte hain. $t$ mein, yeh palindrome $s$ mein even-length hai, toh $t$ mein uska center ek # hai. Uska radius $t$ mein original length ke barabar hai, toh us center par $P [k] = 10$ . Palindrome geeksskeeg $s$ -index 3 par start hota hai (f o r g..., g index 3 hai). Mapping: start = (k - P[k]) // 2. Humein chahiye (k - 10)//2 = 3, toh $k - 10 = 6$ , yani $k = 16$ . Woh $t$ -index do s characters ke beech ka # hai — true even center. ✓ Final answer: longest palindromic substring = ==geeksskeeg, length 10==. Yeh Longest Palindromic Substring se match karta hai via s[start:start+P[k]] = s[3:13]. ✓

Recall Self-check: paanch ek-line reveals

$s$ mein, $P [i]$ kiske barabar hai? ::: t[i] par centered palindrome ki exact length ke, $s$ mein. Sirf $P [2 C - i]$ ki jagah $min (P [2 C - i], R - i)$ kyun? ::: Kyunki symmetry sirf wall $R$ tak guaranteed hai; usse aage verify karna padta hai. Woh ek quantity kaunsi hai jo algorithm ko $O (n)$ banati hai? ::: Wall $R$ sirf rightward move karta hai, total $m$ steps se zyada nahi. $t$ -index $k$ ko radius $P [k]$ ke saath $s$ start-index mein map karo. ::: start = (k - P[k]) // 2. # separators kyun insert karte hain? ::: Yeh har palindrome ko odd-length banate hain toh sirf ek case handle hota hai.