3.8.9 · D1Palindrome algorithms — Manacher's algorithm
Ek palindrome aage se padhne par aur peeche se padhne par same hota hai, matlab yeh apne center ke baare mein ek mirror hai. Agar aap pehle se jaante hain ki ek bada mirror-region exist karta hai, toh us region ke andar har point ka ek twin dusri taraf hota hai — toh dobara measure karne ki jagah, aap apne twin ka answer copy karte hain aur fresh work sirf frontier pe karte hain.
Yeh page assume karta hai ki aapne kuch bhi nahi dekha. Hum har letter, bracket, aur idea ko build karte hain jis par parent note (Palindrome algorithms — Manacher's algorithm (index 3.8.9) ) rely karta hai, un ke dependency order mein. End tak aap us note ki har line bina ruke padh sakte hain.
Definition String aur indexEk string characters ki ek row hoti hai jo left se right likhi jaati hai, jaise boxes ki ek row jisme har box mein ek letter hota hai. Hum ise s Length n index hota hai — ek house number — jo 0 s = a b b a , n = 4 s [ 0 ] = a s [ 1 ] = b s [ 2 ] = b s [ 3 ] = a
Intuition Count 0 se kyun start karte hain?Kyunki "index" ka matlab hai "mere left mein kitne boxes hain." Pehle box ke left mein zero boxes hain, toh woh box 0
Yeh topic ko kyun chahiye? Har baad ka idea — center, radius, mirror — ek statement about indices hai. Agar indices shaky hain, toh unke upar kuch bhi khada nahi rahega.
Ek string ek palindrome hai agar use left-to-right padhne par wahi cheez milti hai jo right-to-left padhne par milti hai. aba, abba, racecar, aur ek single letter x sab palindromes hain. ab nahi hai.
Jo picture important hai woh hai ek center line ke baare mein symmetry : string ko aadha fold karo aur dono halves exactly ek doosre ke upar land karti hain.
Intuition Center ke do flavours
Odd length (aba): fold line ek character par land karti hai — beech wala b. Ek saccha center box exist karta hai.Even length (abba): fold line do characters ke beech land karti hai — dono bs ke beech mein. Koi single center box nahi hota.
Yahi split woh poora reason hai jis wajah se parent note baad mein # trick introduce karta hai: yeh dono flavours ko ek real center box dene par majboor karta hai.
Topic ko yeh kyun chahiye: poora algorithm hai "har possible center ke liye, mirror kitni door tak hold karta hai?" Aapko pehle crystal clear hona chahiye ki center kya hota hai aur uske do kinds hote hain.
Definition Center aur radiusEk center pick karo. Radius woh hai ki center ke har side mein kitne characters hain jo abhi bhi palindrome form karte hain. Agar aap r r r
aba centered on b: radius 1 a har side mein).x akela: radius 0
Topic ko yeh kyun chahiye: algorithm jo array build karta hai, P [ i ] i
t # insert karo, aur ek start mein aur end mein:
abba → t = #a#b#b#a# t m = 2 n + 1 #, plus ek final #).
Intuition Yeh even/odd headache kyun fix karta hait # strictly alternate karte hain. Yeh force karta hai ki t har palindrome ki length odd ho — uska center hamesha t s bb) ab dono bs ke beech wale # par centered hota hai. Toh reason karne ke liye sirf ek hi tarah ka center hota hai.
Topic ko yeh kyun chahiye: yeh do messy cases ko ek uniform loop mein convert karta hai. Yeh reference code mein sabse zyada reuse hone wala idea hai (t = '#' + '#'.join(s) + '#').
Definition Reflection formulaIndex C i C i mirror (twin) hai
i ′ = 2 C − i i ′ C left mein utna hi door hai jitna i
2 C − i C i ( i − C ) C − ( i − C ) = 2 C − i
Topic ko yeh kyun chahiye: symmetry ka matlab hai "point i i ′ copy karne ke liye, aapko jaanna hoga ki twin kaunsa index hai . Woh index 2 C − i
Definition Current rightmost palindromeJab algorithm left se right sweep karta hai, woh ek known palindrome yaad rakhta hai jo sabse door right tak pahunchta hai, jo store hota hai as:
C R R = i + P [ i ]
R − i i symmetry guarantee kitni door tak abhi bhi pahunchti hai.
Intuition "Rightmost" kyun aur "biggest" kyun nahi?Kyunki sweep rightward move karta hai, woh palindrome jis ka right edge sabse aage tak pahunchta hai, woh most likely woh hai jo next point i contain karta hai. Containment hi woh cheez hai jo aapko twin copy karne deta hai. Uski size irrelevant hai; uski reach sab kuch hai.
Topic ko yeh kyun chahiye: min(P[2C-i], R-i) — algorithm ka dil — dono R C C , R
min ( a , b )
min yahan sahi tool kyun hai
Twin ka radius P [ i ′ ] promise hai — "kam se kam itni door tak, mera tumhara match karta hai." Lekin woh promise sirf known window ke andar hi trustworthy hai; wall R
jo twin promise karta hai, P [ i ′ ]
wall kitni door hai, R − i
Hum wall ke baad kabhi claim nahi karte, lekin us tak trust zaroor karte hain. Yahi exactly woh hai jo min(P[i'], R-i) kehta hai.
Topic ko yeh kyun chahiye: yeh single min hi woh cheez hai jo initial guess ko fresh count ki jagah O ( 1 )
Intuition Wall ki travel se work count karnamin guess ke baad, algorithm wall ke past expand karne ki koshish karta hai, ek character ek time. Har successful expansion step R R 0 increase hota hai, at most m = 2 n + 1 run mein , expansion at most m n O ( 1 ) Amortized Analysis hai.
Topic ko yeh kyun chahiye: yeh poora "O ( n ) Expand Around Center ke O ( n 2 )
string s and index from 0
palindrome = symmetry about a center
hash transform to t makes all odd
radius array P equals length in s
mirror index i prime = 2C minus i
window C and R the known reach
min of twin and wall gives cheap guess
expand past wall pushes R right
Related destinations jab aap ready hon: Longest Palindromic Substring , Expand Around Center , aur cousins jo same "copy from a known prefix" trick reuse karte hain — Z-Algorithm , KMP failure function , aur Palindromic Tree (Eertree) .
Kya aap s = "abcd" ke liye s[2] ki value aur n s [ 2 ] = c n = 4
abba odd- ya even-length palindrome hai, aur uska center kahan hai?Even; center dono bs ke beech mein hai (koi single center box nahi).
racecar palindrome ka apne center e ke baare mein radius kya hai?Radius 3 rac); length = 2 ⋅ 3 + 1 = 7
abc ko # trick se transform karo.#a#b#c# m = 2 ⋅ 3 + 1 = 7
Agar t P [ i ] = 4 s Length 4 t s
Center C = 5 i = 8 i ′ i ′ = 2 ⋅ 5 − 8 = 2
Window mein R = 9 i = 6 P [ i ′ ] = 5 min ( 5 , R − i ) = min ( 5 , 3 ) = 3
Manacher O ( n ) O ( n 2 ) Kyunki expansion sirf R R m
