Palindrome algorithms — Manacher's algorithm

3.8.9 · Coding › String Algorithms

KYA problem solve kar rahe hain?

KYO `#` trick (transformation)

Agar t ki length $m = 2 n + 1$ hai, toh hum ek array $== P [i] ==$ compute karte hain = t[i] par centered longest palindrome ka radius (radius = t mein har side par characters ki sankhya).

KAISE: core recurrence (derive karo)

Hum $i$ ko left se right sweep karte hain aur ab tak mila sabse rightmost-reaching palindrome maintain karte hain, jise uske center $C$ aur right boundary $R$ se describe kiya jaata hai (toh yeh $[C - (R - C), R]$ cover karta hai, matlab half-length $R - C$ ).

KYO $min$ — do cases (dono ko steel-man karo)

Isliye hum $min (P [i^{'}], R - i)$ lete hain: mirror par trust karo, lekin wall ke aage kabhi trust mat karo.

Figure — Palindrome algorithms — Manacher's algorithm

Reference implementation

def manacher(s):
    t = '#' + '#'.join(s) + '#'        # length 2n+1
    m = len(t)
    P = [0]*m
    C = R = 0
    for i in range(m):
        if i < R:
            P[i] = min(P[2*C - i], R - i)   # mirror, capped at wall
        # expand
        while i - P[i] - 1 >= 0 and i + P[i] + 1 < m and \
              t[i - P[i] - 1] == t[i + P[i] + 1]:
            P[i] += 1
        # update rightmost
        if i + P[i] > R:
            C, R = i, i + P[i]
    return P   # P[i] = palindrome length in ORIGINAL s centered at t[i]
 
# longest palindromic substring:
def longest_pal(s):
    P = manacher(s)
    k = max(range(len(P)), key=lambda i: P[i])
    start = (k - P[k]) // 2          # map t-index back to s-index
    return s[start:start + P[k]]

Worked examples

Worked example

s = "abba", t = "#a#b#b#a#" par trace (indices 0..8)

i	t[i]	mirror $i^{'}$	init $P [i]$	after expand
0	#	—	0	0
1	a	—	0 (i≥R)	1 → set C=1,R=2
2	#	0	min(0,0)=0	0
3	b	—	0	1 → C=3,R=4
4	#	i'=2, P=0	min(0,0)=0	expand! `t[3]=b=t[5]=b`, phir `t[2]=#=t[6]=#`, phir `t[1]=a=t[7]=a`, phir `t[0]=#=t[8]=#` → P=4, C=4,R=8
5	b	i'=3, P=1	min(1, R-i=3)=1	1
6	#	i'=2, P=0	min(0,2)=0	0
7	a	i'=1, P=1	min(1,1)=1	1
8	#	i'=0, P=0	min(0,0)=0	0

i=4 par kyun? Center par # hai, mirror 0 deta hai, lekin yeh $R$ par hai, toh hume expand karna hoga — aur hum poora abba discover karte hain (P=4). Length 4 = full palindrome. ✓ i=5 par kyun? Mirror $i^{'} = 3$ ka $P = 1$ tha aur $P [i^{'}] = 1 < R - i = 3$ , toh Case A: hum 1 copy karte hain aur expand karne ki koshish nahi karte. Yahi speedup action mein hai.

Common mistakes

Recall Feynman: ek 12-saal ke bachche ko explain karo

Ek row of mirror tiles ki imagine karo jahan beech mein ek magic mirror hai. Agar tumhe pehle se pata hai ki left side right side ko perfectly reflect karti hai, toh kisi jagah kya hai yeh jaanne ke liye, tum firse measure karne ke bajay uske mirror buddy ko dekh sakte ho. Tum real measuring sirf bilkul edge par karte ho jahan mirror ka reflection khatam ho jaata hai. Kyunki woh edge sirf aage move karti hai, tum kabhi same ground ko dobara measure nahi karte — isliye poora kaam fast hai. # symbols sirf spacers hain jo hum sprinkle karte hain taaki "even-length" mirrors aur "odd-length" mirrors ek jaisi shape ban jayein aur hume sirf ek tarah se deal karna pade.

Flashcards

s ko #a#b#...# mein kyun transform karte hain?

Yeh naye string mein har palindrome ko odd-length banne par force karta hai, odd/even cases ko unify karta hai (center hamesha ek position hoti hai).

P [i]

kya store karta hai, aur yeh original string se kaise relate karta hai?

Transformed t mein radius; numerically original s mein corresponding palindrome ki length ke barabar hai.

C

center ke baare mein

i

ka mirror index kya hai?

i^{'} = 2 C - i

i < R

ke liye Manacher initialization state karo.

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

, phir expand karo.

R - i

ke saath

min

kyun?

Symmetry sirf right wall

R

tak guarantee karta hai; us se aage koi info nahi hai, isliye hum cap karte hain aur manually expand karte hain.

Tum kab expand NAHI karte?

Jab mirror palindrome strictly bade waale ke andar fit hota hai (

P [i^{'}] < R - i

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

exactly hota hai.

Tum

(C, R)

kab update karte ho?

Jab

i + P [i] > R

, set karo

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

Manacher

O (n)

kyun hai?

Mirror copy

O (1)

hai; expansion sirf

R

ko aage move karta hai, aur

R

monotonically

0

\leq 2 n + 1

tak badhta hai, toh total expansion

O (n)

hai.

Transformed center index

k

ko s mein start index par map karo.

start = (k - P[k]) // 2.

t[i] par kitne palindromic substrings centered hain?

⌈ P [i] /2 ⌉

Connections

Longest Palindromic Substring (DP $O (n^{2})$ vs Manacher $O (n)$ )
Expand Around Center (woh naive baseline jise Manacher accelerate karta hai)
Z-Algorithm & KMP failure function (dusre linear string preprocessing jo prior work ke reuse use karte hain)
Palindromic Tree (Eertree) (distinct palindromes count karne ka alternative)
Amortized Analysis (kyun monotone $R$ argument linear time deta hai)