Palindrome algorithms — Manacher's algorithm: Visual walkthrough

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

Hum poori tarah neeche ek hi sawaal ka jawaab dhundh rahe hain:

"String ke har jagah par, uske around palindrome kitna door tak jaata hai — bina woh ground dobara check kiye jo hum pehle hi check kar chuke hain?"

Step 1 — Palindrome kya hai, mirror ki tarah draw karo

KYA HAI. Palindrome woh string hai jo aage se aur peeche se ek jaisi padhti hai: racecar, abba, b. Ek center choose karo aur string apne aap ka mirror image hai us center ke around.

Hum center ki kyun parwah karte hain. Har palindrome ka ek middle hota hai. Agar hum jaante hain, har possible middle ke liye, mirroring kitni door tak jaati hai, toh hum string ka har palindrome jaante hain. Toh poora problem ban jaata hai: har center ke liye, radius dhundho.

TASVEER. Neeche, abcba ko uske center c par draw kiya gaya hai. Green arrows dikhate hain ki position $c - 1$ , $c + 1$ ke equal hai, aur $c - 2$ , $c + 2$ ke equal hai. Radius woh matched pairs ki count hai jo mirror toootne se pehle milti hai — yahan yeh $2$ hai.

Figure — Palindrome algorithms — Manacher's algorithm

Do irritating flavors hain: odd palindromes (aba, center ek letter hai) aur even wale (abba, center do letters ke beech ki jagah hai). Hum isko aage fix karte hain.

Step 2 — `#` trick: har palindrome ko odd banao

KYA HAI. Har character ke beech mein aur dono ends par ek spacer # daalo. abba ban jaata hai #a#b#b#a#. Hum is nayi string ko $t$ kehte hain.

KYU. Even palindrome ka center do characters ke beech hota hai — koi single index nahi hota jis par khada ja sake. Padding ke baad, woh "beech ki jagah" ab ek asli # se occupy ho jaati hai. Toh $t$ mein har palindrome ek actual index of $t$ par centered hota hai, aur har ek ki odd length hoti hai. Do cases ki jagah ek uniform case.

TASVEER. Upar ki row abba hai. Neeche ki row $t =$ #a#b#b#a# hai. Purana even center (do bs ke beech ki gap) ab index $4$ par highlighted # hai — ek real position jis par khada ja sakte hain.

Related tools jo "find longest palindrome" task ko zyada slowly solve karte hain: Longest Palindromic Substring aur Expand Around Center — hum dono ko beat karne wale hain.

Step 3 — Slow tarika, aur exactly kyun takleef deta hai

KYA HAI. Naive method: har center $i$ par khade ho, aur ek ek step baahir expand karo, $t [i - k]$ ko $t [i + k]$ se compare karte hue jab tak woh differ na karein. Yeh Expand Around Center hai.

YEH correct kyun hai lekin slow kyun hai. Yeh obviously correct hai. Lekin aaaa dekho. Har center almost poori string tak expand kar sakta hai, toh hum roughly $\frac{m}{2}$ centers par $\frac{m}{2}$ comparisons karte hain → lagbhag $\frac{m ^{2}}{4}$ kaam. Yeh $O (n^{2})$ hai.

TASVEER. Red brackets aaaa#-style input ke teen alag centers par expansion dikhate hain. Notice karo massive overlap — wahi characters baar baar compare hote hain. Woh bekar re-comparison hi woh dushman hai jise hum ab eliminate karenge.

Step 4 — Sabse rightmost palindrome: jo memory hum carry karte hain

KYA HAI. Jab hum $i$ ko left se right sweep karte hain, hum woh single palindrome yaad rakhte hain jo ab tak mila hai aur sabse zyada right tak pahuncha hai. Hum ise do numbers mein store karte hain:

== $C$ == — $t$ mein uska center index.

== $R$ == — uske right edge ke baad wali index (uski right boundary).

YEH DO KYUN. $C$ par centered palindrome jiska right edge $R$ hai woh $R - C$ steps dono taraf tak jaata hai, toh woh interval $[2 C - R, R]$ cover karta hai. $(C, R)$ jaanne se hum exactly jaante hain $t$ ka kaunsa region "symmetry se pehle se samjha hua" hai. Trick ke baare mein sab kuch isi region ke andar hota hai.

TASVEER. Blue palindrome number line par baitha hai. $C$ uska center hai, $R$ uski right wall hai, aur $2 C - R$ uski left wall hai ( $R$ ko $C$ ke across reflect karke milti hai). Shaded band haara "known-mirror zone" hai.

Step 5 — Mirror copy, aur woh wall jo ise limit karti hai

KYA HAI. Maano haara naya center $i$ blue palindrome ke andar hai, yaani $i < R$ . Uska mirror buddy $i^{'} = 2 C - i$ hai, jise hum pehle visit kar chuke hain (woh left par hai). Hum tentatively $P [i] = P [i^{'}]$ set karte hain.

KYU. Blue palindrome ke andar, position $i$ aur position $i^{'}$ mirror images hain. Jo palindrome $i^{'}$ par exist karta hai woh $i$ par reflect hota hai — jab tak woh reflected palindrome blue walls ke andar rahe. Lekin agar $P [i^{'}]$ itna bada hai ki mirrored palindrome $R$ se aage nikal jaaye, toh waahan koi guarantee nahi hai: symmetry sirf wahi promise karti hai jo blue region ke andar hai. Toh hum copy ko wall tak ki distance yaani $R - i$ par cap karna chahiye.

TASVEER. Do scenarios side by side.

Left (Case A): buddy ka palindrome (yellow) strictly blue walls ke andar fit hota hai. Uska mirror $i$ par (bhi yellow) ek exact, complete copy hai. $P [i] = P [i^{'}]$ , aur koi expansion possible nahi hai.

Right (Case B): buddy ka palindrome left wall $2 C - R$ se milta hai (ya aage nikal jaata hai). Uska mirror $i$ par sirf right wall $R$ tak guaranteed hai. $R$ ke aage hum blind hain, toh hum $R - i$ par cap karte hain aur expand karna padega.

Step 6 — Wall ke baad expand karo (sirf jab zaroorat ho)

KYA HAI. Mirror copy ke baad, hum aage push karne ki koshish karte hain: jab tak hamare current radius ke bilkul baahr ke characters match karte rahen — $t [i - P [i] - 1] = t [i + P [i] + 1]$ — $P [i]$ ko ek se badhao.

YEH sirf kabhi kabhi kyun. Case A mein copy pehle se maximal hai; pehla comparison fail ho jaata hai, toh loop zero kaam karta hai. Case B mein hum genuinely $R$ se aage unknown territory mein extend kar sakte hain — wahi jagah hai jahan real comparisons hote hain. Phir, agar haara naya right edge $i + P [i]$ purane $R$ se aage jaata hai, toh humne ek naya rightmost palindrome dhundha hai, toh hum $C = i$ , $R = i + P [i]$ update karte hain.

TASVEER. Ek Case-B center. Yellow part (wall tak) mirror se free mila. Green part woh nayi expansion hai $R$ ke baad, jo real comparisons se discover ki gayi. Red wall $R$ phir right mein naye edge tak jump karta hai.

Step 7 — Total kaam $O (n)$ kyun hai (amortized)

KYA HAI. Poore run mein saare expansion comparisons add karo.

YEH linear kyun hai. Mirror step $O (1)$ hai har index ke liye — koi loop nahi. Sirf expand loop hai, aur waahan har successful comparison $R$ ko ek step right move karta hai. $R$ $0$ par start hota hai aur kabhi decrease nahi karta, aur yeh at most $m$ tak pahunch sakta hai. Toh poore algorithm mein, expand loop at most $m$ successful steps total chalaata hai — har index par nahi, total. Plus har center par ek failed comparison. Grand total $O (m) = O (n)$ .

TASVEER. $R$ ki value sweep index $i$ ke against plot ki gayi hai. Yeh ek monotone staircase hai jo $0$ se $m$ tak climb karti hai. Climbing ka area = total expansion kaam = $m$ se bounded hai. Yeh wahi accounting idea hai jo Amortized Analysis mein hai.

Step 8 — Degenerate cases, taaki kuch surprise na kare

KYA HAI. Woh corners jo naive code tod dete hain.

Worked example Har case, walk-through

$i \geq R$ (known zone ke baahir): copy karne ke liye koi mirror nahi. $P [i] = 0$ se start karo aur scratch se expand karo. Aise hi pehla center shuru hota hai.
Single character s = "a" → $t =$ #a#. a par center expand hota hai #a# tak, $P = 1$ . Length $1$ . ✓
Sab same s = "aaaa": almost har center apne buddy se free mein copy karta hai; expansion sirf tab fire karta hai jab woh $R$ ko previous max se aage push kar sake, toh total expansion $\approx n$ hai, $n^{2}$ nahi. Linearity confirmed.
Koi repeats nahi s = "abcd": har real center ka $P = 1$ hai, har # center ka $P = 0$ hai. Wall ek ek step aage badhti hai; phir bhi $O (n)$ .
Empty string: $t =$ #, $m = 1$ , ek index par loop $P = [0]$ deta hai, longest palindrome "" hai. Koi crash nahi.
Boundary guards: expand loop ko check karna chahiye $i - P [i] - 1 \geq 0$ aur $i + P [i] + 1 < m$ warna yeh $t$ ke ends ke bahar read karta hai.

TASVEER. Char tiny strings — a, aa, abc, aaaa — har ek ka final $P$ array neeche print kiya gaya hai, taaki tum har regime mein pattern dekh sako.

Ek tasveer mein summary

TASVEER. Poora algorithm ek canvas par: blue rightmost palindrome $(C, R)$ , uske andar ek naya center $i$ , uska mirror buddy $i^{'}$ , free copy (yellow) wall par capped, paid expansion (green) $R$ ke baad, aur wall apni nayi jagah par jump karti hui. Yeh akeli diagram hi Manacher's algorithm hai.

Related structures jo palindromes enumerate karte hain: Palindromic Tree (Eertree). Mirror/reuse idea Z-Algorithm aur KMP failure function ko echo karta hai — teeno amortize karte hain ek "reach so far" boundary carry karke.

Recall Feynman: poori walkthrough plain words mein retell karo

Hamare paas ek string thi aur hum chahte the ki har possible middle ke liye, mirror reflection kitni door tak jaati hai. Even-length mirrors irritating the, toh humne # spacers chidak diye taaki har mirror odd ho jaaye — ek clean shape. Phir humne notice kiya: agar ek bada mirror pehle se haari nayi jagah cover karta hai, toh us bade mirror ka left side pehle se measure ho chuka hai, aur symmetry se woh right side ke equal hai. Toh hum sirf mirror buddy par jhaank ke uska answer copy karte hain — free mein — lekin sirf utna door jitna bade mirror ki wall tak hai; wall ke baad hum kuch nahi jaante. Jahan buddy ka answer wall se takraata hai, hum apni sleeves roll up karte hain aur haath se measure karte hain, ek ek step, wall ko aage push karte hain. Kyunki wall sirf aage jaati hai aur sirf string ki length jaisi door ja sakti hai, poore run mein saara haath se measuring sirf ek pass mein jud jaata hai. Mirror karo jab kar sako, wall push karo jab karna pade — linear time.

Recall Self-check

s="abba" par t="#a#b#b#a#" ke saath, $P [4]$ kya hai aur kyun? ::: $P [4] = 4$ : index 4 par center #, mirror 0 deta hai lekin hum exactly wall par baithe hain, toh hum expand karna padega — aur hum poora abba uncover karte hain, radius/length $4$ . Mirror step $R - i$ par capped kyun hai? ::: Symmetry sirf woh guarantee karti hai jo rightmost palindrome ke andar hai; wall $R$ ke baad haare paas koi information nahi hai, toh hum usse aage copy nahi kar sakte. Total expansion $O (n)$ kyun hai? ::: Har successful expand comparison $R$ ko ek step right push karta hai; $R$ kabhi retreat nahi karta aur maximum $m$ tak jaata hai, toh total expansions $\leq m$ hain.