Palindrome algorithms — Manacher's algorithm: Question bank

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

Shuru karne se pehle, ye paanch names yaad karo jinhein kabhi confuse nahi karna:

$C$ — abhi tak mila sabse door tak pahunchne wala palindrome ka center.
$R$ — us palindrome ki right boundary (the "wall"): $R$ tak sab kuch $C$ ke baare mein symmetric hai, $R$ ke baad kuch bhi guarantee nahi.
$i$ — wo position jise hum abhi solve kar rahe hain.
$i^{'} = 2 C - i$ — $C$ ke across $i$ ka mirror (uska "buddy" doosri taraf).
$P [i]$ — padded string $t$ mein $i$ par center wale sabse lambe palindrome ka radius.

Neeche ki picture ek nazar mein paanchon ko fix karti hai — jab bhi koi sawal wall ya mirror ka zikr kare, wapas dekho.

Figure — Palindrome algorithms — Manacher's algorithm

True or false — justify karo

TF1. "# transform ke baad,

t

mein kuch palindromes abhi bhi even length ke hain."

False —

t

mein har palindrome odd length ka hota hai, kyunki characters aur # strictly alternate karte hain isliye kisi bhi palindrome ka center ek single position hota hai, jo ek symmetric shape

2 r + 1

wide deta hai.

TF2. "

P [i]

(

t

mein radius)

s

mein real palindrome ki length ke barabar hota hai."

True — radius-

r

palindrome

t

mein

2 r + 1

positions span karta hai jismein exactly

r

real characters hain, toh original length precisely

P [i]

hoti hai.

TF3. "Known palindrome ke andar,

P [i]

hamesha exactly

P [i^{'}]

hota hai."

False — ye exactly

P [i^{'}]

hota hai tabhi jab mirror palindrome strictly wall ke andar fit ho; agar ye wall ko touch ya cross kare toh hum sirf itna jaante hain ki

P [i] \geq R - i

aur expand karna padega.

TF4. "Ek baar

C = i, R = i + P [i]

set kar diya, to

R

baad mein decrease ho sakta hai."

False —

R

monotonically non-decreasing hai; hum ise sirf tab update karte hain jab

i + P [i] > R

ho, yaani strictly rightward, aur yahi reason hai ki algorithm

O (n)

hai.

TF5. "Expand loop ek single index

i

ke liye

Θ (n)

baar run ho sakta hai."

Ek akele index ke liye True hai, lekin har expansion step

R

ko ek aage push karta hai aur

R

kabhi peeche nahi jaata, isliye poori sweep mein total expansion work

O (n)

hai — "har unit of work ko ek aage badhne wali boundary pe charge karo" wala argument exactly Amortized Analysis hai.

TF6. "Manacher sirf sabse lambe palindrome ke liye nahi, har center ke liye answer deta hai."

True — array

P

mein

2 n + 1

centers mein se har ek ke liye ek value hai, toh saare palindromic substrings count karna ya sabse lamba dhundhna dono

P

par ek pass mein ho jaate hain.

TF7. "Expand-Around-Center aur Manacher worst case mein equally fast hain."

False — Expand Around Center, jo simpler cousin hai aur har center ko scratch se re-measure karta hai,

O (n^{2})

hai (identical letters ki string har baar full re-expansion force karti hai); Manacher mirror answers reuse karke

O (n)

mein rehta hai.

TF8. "Agar

i \geq R

hai toh bhi hum mirror se copy kar sakte hain."

False — jab

i

wall par ya uske aage ho toh koi surrounding known palindrome nahi hota jismein se reflect kar sakein, isliye

P [i]

0

se start karke scratch se expand karna padta hai.

TF9. "Mirror index

i^{'} = 2 C - i

hamesha ek valid (non-negative) index hota hai jab bhi

i < R

ho."

True — agar

i < R

hai toh

i

[2 C - R, R]

ke andar hai, isliye uska reflection

i^{'}

bhi usi interval mein hai, jo string bounds ke andar hai.

Error dhundho

SE1. Koi P[i] = P[2*C - i] bina cap ke likhta hai. Ye galat kyun hai?

Mirror palindrome bade palindrome ki left edge ke baad tak nikl sakta hai, jahan symmetry koi guarantee nahi deti; tumhe

min (P [2 C - i], R - i)

se cap karna hoga aur phir expand karna hoga.

SE2. Koi best

t

-index ko

s

mein map karne ke liye start = k - P[k] likhta hai. Fix karo.

Ye (k - P[k]) // 2 hona chahiye, kyunki

t

roughly do guna dense hai (har pair ke beech ek #), isliye ek

t

-offset ko

s

-offset banana ke liye half karna padta hai.

SE3. Expand loop hai while t[i-P[i]-1] == t[i+P[i]+1]: bina bound check ke. Kya toot ta hai?

String ke ends par ye out of range index karta hai; tumhe i-P[i]-1 >= 0 and i+P[i]+1 < m chahiye (yaad raho

m = 2 n + 1

t

ki length hai) chahe # padding boundary ko thoda soft kare.

SE4. Koi cap mein wall ko R-i-1 likhta hai R-i ki jagah. Kya galat hota hai?

Ek off-by-one jo mirror ko ek character se under-trust karta hai, ek unnecessary expansion step force karta hai aur boundary par possibly galat (too-short) copy deta hai — sahi cap exactly

R - i

hai.

SE5. Koi C,R = i, i+P[i] unconditionally har iteration mein update karta hai. Ye bug kyun hai?

Update sirf tab karo jab i+P[i] > R ho; warna center ko ek chhote palindrome par move kar sakte ho aur reach shrink ho sakti hai, jisse ye invariant destroy ho jaata hai ki

[C, R]

sabse rightmost reach hai.

SE6. Koi i' = C - (i - C) se reflect karta hai aur sochta hai ye 2C - i se alag hai.

Dono identical hain:

C - (i - C) = 2 C - i

; "distance from

C

" wali phrasing aur algebraic form ek hi mirror hain.

SE7. Koi

t

ko '#'.join(s) se banata hai (leading/trailing # nahi). Kya fail hota hai?

Pehle aur aakhri real characters ek # neighbour kho dete hain, isliye ends par palindromes symmetrically expand nahi kar paate aur boundary radii galat aate hain; tumhe '#' + '#'.join(s) + '#' chahiye.

Why questions

WHY1. # trick odd aur even palindromes ko unify kyun karti hai?

s

ka ek even palindrome

t

mein ek # par centered odd palindrome ban jaata hai, aur odd wala ek real char par center hota hai — isliye

t

mein sirf ek case (odd) handle karna padta hai.

WHY2. Recurrence

min

kyun hai, sirf

P [i^{'}]

kyun nahi?

Hum mirror ko sirf itna trust karte hain jitna wall tak pahunchta hai;

min (P [i^{'}], R - i)

mirror ka promise leta hai lekin

R - i

par clip karta hai jahan hamari symmetry knowledge khatam hoti hai.

WHY3. Case A mein (mirror strictly andar fit ho), hum sure kyun ho sakte hain ki koi expansion help nahi karegi?

Agar

P [i]

grow kar sakta, toh symmetry uske mirror

P [i^{'}]

ko bhi grow karne par force karti — lekin

P [i^{'}]

already maximal hai, contradiction hai, isliye exactly

P [i] = P [i^{'}]

hota hai.

WHY4. Case B mein (mirror wall ko hit/cross kare), hum character by character expand kyun karte hi hain?

R

ke baad

C

ke dono sides guaranteed equal nahi hain, isliye mirror ki extra length unverified hai; sirf

R

ke aage real comparisons hi ise confirm kar sakti hain.

WHY5. Amortization total expansion ko

O (n)

kyun rakhta hai jabki ek index bahut zyada expand kar sakta hai?

Har successful expansion step

R

ko ek aage badhata hai aur

R

sirf increase karta hai, isliye saare expansion steps ka sum

R

ki total travel

\leq m

se bounded hai — "har unit of forward progress ke liye pay karo" wala accounting Amortized Analysis ka dil hai.

WHY6.

t [i]

par centered palindromic substrings ki count

⌈ P [i] /2 ⌉

kyun hoti hai?

Har real-palindrome layer

t

mein ek odd radius value correspond karti hai;

P [i]

tak those layers count karne par radius ka ceiling of half milta hai.

WHY7. Manacher conceptually Z-Algorithm aur KMP failure function se related kyun hai?

Teeno ek "farthest useful boundary" maintain karte hain aur recompute karne ki jagah pehle se computed structure reuse karte hain — Z-Algorithm ka Z-box aur KMP failure function ke borders, Manacher ke wall

R

jaisa hi role play karte hain.

WHY8. Sirf Longest Palindromic Substring ke liye Manacher ko Palindromic Tree (Eertree) se prefer kyun karein?

Manacher ek tiny array-only

O (n)

pass hai bina kisi tree structure ke; Palindromic Tree (Eertree) har distinct palindrome store karne ka cost pay karta hai — ye richer information tab chahiye nahi jab goal sirf ek Longest Palindromic Substring hai.

Edge cases

EC1. Empty string s = "" ke liye Manacher kya return karta hai?

t =

"#" (length 1), ek center ka

P = 0

hota hai, isliye koi palindrome nahi aur longest empty string hai.

EC2. Single character s = "a" ke liye

P

kya hai?

t =

"#a#"; a par center expand karne ki koshish karta hai lekin dono neighbours outer # aur # hain jo match karte hain, radius

P = 1

milta hai — sahi se length-1 palindrome a recover hota hai.

EC3. s="aaaa" jaisi all-same string mein, har index ek bada expansion kyun trigger nahi karta?

Mirror zyaadatar radii ever-growing palindrome ke andar se predict karta hai, isliye expansion sirf tabhi fire hoti hai jab

R

ko pichle maximum se aage push kar sake — total expansions

\approx n

rehti hain.

EC4. Bina repeats wali string par, jaise s="abcde",

P

kaisa dikhta hai?

Sirf single characters palindromes hain, isliye real-char centers ko

P = 1

milta hai aur # centers ko

P = 0

; sabse lamba palindrome length 1 ka hota hai.

EC5. Bilkul pehle index

i = 0

par (ek #), mirror step kyun nahi hoti?

Shuruaat mein

C = R = 0

hai, isliye

i < R

false hai; koi known palindrome nahi jismein se reflect kar sakein, aur

P [0]

0

se start hota hai.

EC6. Wall par exactly

i = R

wale index mein kya hota hai?

Condition

i < R

fail hoti hai, isliye hum koi mirror value copy nahi karte;

P [i] = 0

se start karte hain aur expand karte hain, phir possibly wall ko aage move karte hain.

EC7. Jab do alag centers ek hi maximal

P

dete hain, longest_pal kaunsa return karta hai?

max(..., key=...) maximum achieve karne wala pehla index return karta hai, isliye ye sabse pehle aane wala longest palindrome return karta hai — ties position se break hoti hain, arbitrarily nahi.

Recall Aage badhne se pehle ek-line self-test

"Mirror karo, phir Wall ko push karo." Agar tum bata sako min kyun aata hai aur $R$ sirf right kyun jaata hai, toh algorithm tumhara hai. Min kyun? ::: Mirror ko trust karo, lekin wall $R$ ke aage kabhi nahi jahan symmetry unverified hai. $O (n)$ kyun hai? ::: Expansion sirf monotone boundary $R$ ko aage badhata hai, isliye total work $R$ ki forward travel se bounded hai.