Palindrome algorithms — Manacher's algorithm

WHAT problem are we solving?

WHY the `#` trick (transformation)

If t has length $m = 2n+1$ , we compute an array $==P[i]==$ = radius of the longest palindrome centered at t[i] (radius = number of characters on each side, in t).

HOW: the core recurrence (derive it)

We sweep $i$ left to right and maintain the rightmost-reaching palindrome found so far, described by its center $C$ and right boundary $R$ (so it covers $[C-(R-C),\, R]$ , i.e. half-length $R-C$ ).

WHY the $\min$ — the two cases (Steel-man both)

That's why we take $\min(P[i'],\, R-i)$ : trust the mirror, but never trust beyond the wall.

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 Trace on

s = "abba", t = "#a#b#b#a#" (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`, then `t[2]=#=t[6]=#`, then `t[1]=a=t[7]=a`, then `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

Why step i=4? # at center, mirror gives 0, but it's at $R$ , so we must expand — and we discover the whole abba (P=4). Length 4 = the full palindrome. ✓ Why step i=5? Mirror $i'=3$ had $P=1$ and $P[i']=1 < R-i=3$ , so Case A: we copy 1 and don't bother expanding. This is the speedup in action.

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine a row of mirror tiles where the middle is a magic mirror. If you already know the left side perfectly reflects the right side, then to know what's at some spot, you can just peek at its mirror buddy instead of measuring again. You only do real measuring at the very edge where the mirror's reflection runs out. Because that edge only ever moves forward, you never re-measure the same ground twice — so the whole job is fast. The # symbols are just spacers we sprinkle in so that "even-length" mirrors and "odd-length" mirrors become the same shape and we only have to deal with one kind.

Flashcards

Why transform s into #a#b#...#?

It forces every palindrome in the new string to be odd-length, unifying odd/even cases (center is always one position).

What does

P[i]

store, and how does it relate to the original string?

Radius in transformed t; numerically equals the length of the corresponding palindrome in the original s.

What is the mirror index of

i

about center

C

i' = 2C - i

State the Manacher initialization for

i < R

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

, then expand.

Why the

\min

with

R-i

Symmetry only guarantees up to the right wall

R

; beyond it we have no info, so we cap and expand manually.

In which case do you NOT expand?

When the mirror palindrome fits strictly inside the big one (

P[i'] < R-i

P[i]=P[i']

exactly.

When do you update

(C,R)

When

i + P[i] > R

, set

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

Why is Manacher

O(n)

Mirror copy is

O(1)

; expansion only moves

R

forward, and

R

rises monotonically from

0

\le 2n+1

, so total expansion is

O(n)

Map transformed center index

k

back to start index in

s

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

How many palindromic substrings are centered at t[i]?

\lceil P[i]/2 \rceil

Connections

Longest Palindromic Substring (DP $O(n^2)$ vs Manacher $O(n)$ )
Expand Around Center (the naive baseline Manacher accelerates)
Z-Algorithm & KMP failure function (other linear string preprocessing using reuse-of-prior-work)
Palindromic Tree (Eertree) (alternative for counting distinct palindromes)
Amortized Analysis (why the monotone $R$ argument gives linear time)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Manacher ka core idea bahut simple hai: palindrome symmetric hota hai, yaani left side right side ka mirror hota hai. Toh agar tumne pehle ek bada palindrome already find kar liya hai, toh uske andar ki har cheez already mirror ho chuki hai. Naya center aata hai toh tum scratch se ginna shuru mat karo — apne mirror position ka answer copy kar lo, aur sirf utna hi expand karo jitna mirror guarantee nahi de raha. Isi reuse ki wajah se naive $O(n^2)$ ban jaata hai fast $O(n)$ .

Pehle ek trick: original string mein # daal do har character ke beech (abba → #a#b#b#a#). Isse saare palindrome odd-length ban jaate hain, toh odd aur even ka alag-alag case handle karne ki tension khatam. Phir array $P[i]$ banao = us center ka palindrome radius. Mazedaar baat: ye radius bilkul original string ke palindrome ki length ke barabar hota hai.

Main formula: agar current $i$ already-known bade palindrome ke andar hai (center $C$ , right wall $R$ ), toh mirror nikaalo $i' = 2C - i$ aur P[i] = min(P[i'], R-i) set karo. min isliye, kyunki wall $R$ ke baad humein kuch pata nahi — symmetry ki guarantee wahin khatam ho jaati hai. Uske baad character-by-character expand karo, aur agar tum $R$ se aage nikal gaye toh $(C,R)$ update kar do.

Kyun fast? Mirror-copy $O(1)$ hai, aur expand loop sirf tab kaam karta hai jab $R$ aage badhta hai — aur $R$ kabhi peeche nahi jaata, sirf $0$ se $2n+1$ tak aage. Toh total expansion $O(n)$ . Exam/interview mein ye dhyaan rakho: min mein wall cap mat bhoolna, aur original index map karte time (k - P[k]) // 2 use karna — ye do hi sabse common galtiyaan hain.

Palindrome algorithms — Manacher's algorithm

WHAT problem are we solving?

WHY the `#` trick (transformation)

HOW: the core recurrence (derive it)

WHY the $\min$ — the two cases (Steel-man both)

Reference implementation

Worked examples

Common mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — String Algorithms

Connections