Algo VisualizedStart learning

Manacher's Algorithm

"Longest palindromic substring" is a classic interview question with an easy O(n²) answer. Manacher's algorithm finds every palindrome in O(n) with the same mirror trick as the Z-function.

advanced⏱ 10 min read

←Builds on

11Naive Pattern MatchingIt starts from expanding around every center, the naive O(n²) idea, and removes the waste.11Rolling Hash & Rabin–KarpHashing a string and its reverse tests any palindrome in O(1), and binary search on top finds every radius in O(n log n); Manacher drops the hash and the log factor.+Z-FunctionManacher reuses the Z-function's rightmost window to start each center from a known answer.

Leads to→

This is where the roadmap ends. Look back at how far you came.

1Learn2Play3Check4Practice
01

Learn

The idea, the mechanics and the cost.

01Palindromes grow from a centre

Every palindrome of odd length has a centre character. Define d1[i] as the radius of the longest odd palindrome centred at i: it covers s[i − d1[i] + 1 .. i + d1[i] − 1] and has length 2·d1[i] − 1.

For abacaba, d1 = [1, 2, 1, 4, 1, 2, 1]. The centre c has radius 4: the whole string.

The simple method expands around every centre while the two outer characters are equal. That is easy and often fine, but on aaaa…a every centre expands far, giving O(n²). Note also that a palindrome of radius r contains palindromes of radius r − 1, r − 2, … around the same centre, so d1[i] also counts the palindromes centred at i.

a0b1a2c3a4b5a6d11214121centre 3, radius 4 → "abacaba", length 2·4 − 1 = 7

02The mirror inside [l, r]

Keep [l, r], the palindrome found so far that reaches furthest right. A palindrome reads the same in both directions, so whatever happens around position i inside it also happened around its mirror j = l + r − i.

  • If i ≤ r: start from k = min(d1[j], r − i + 1). The cap is needed because beyond r the mirror tells you nothing.
  • Otherwise start from k = 1.
  • Then expand while s[i − k] = s[i + k], and if the palindrome now reaches past r, update [l, r].

Just like the Z-function, every successful expansion moves r to the right and r never moves back. The total work is therefore O(n).

rightmost palindrome [l, r] = [0, 6]a0b1a2c3a4b5a6mirror: l + r − i = 0 + 6 − 5 = 1d1[5] starts from d1[1] = 2

03Even palindromes and uses

Palindromes of even length, like abba, have their centre between two characters. You can compute a second array d2 with the same idea, or use a simpler trick: insert a separator between all characters, #a#b#b#a#. Now every palindrome in the new string has odd length, so one run of d1 handles both kinds. Divide the radii by two to get lengths in the original string.

Typical uses:

  • longest palindromic substring
  • counting all palindromic substrings: the sum of the radii
  • checking in O(1) whether any substring s[l..r] is a palindrome after O(n) preprocessing
"abba" has its centre between two lettersabbainsert #, and the centre becomes one cell#a#b#b#a#

Cost at a glance

Expand around every centreO(n²)
ManacherO(n)
MemoryO(n)

Remember

  1. d1[i] is the radius of the longest odd palindrome centred at i; its length is 2·d1[i] − 1.
  2. Inside the rightmost palindrome [l, r], start from the mirror's radius capped at the edge; r only moves right, so the run is O(n).
  3. Inserting # between characters turns even palindromes into odd ones, so one array covers both.
02

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch for "mirror" steps: the radius starts from a copied value, and only the part beyond the boundary is compared.

Interactive visualizerfocus here, then space ← →
✎ Your inputUp to 12 characters, e.g. a word with a palindrome inside: xabacabay.

Manacher's algorithm

abacaba

d1 (radius)

abacaba
d1·······
Manacher finds every palindrome in O(n). d1[i] = radius of the longest odd length palindrome centered at i. Keep the rightmost known palindrome [l,r].

Pseudocode

 1 d1[i] = radius of the longest odd palindrome centered at i 2 maintain the rightmost palindrome [l,r] 3 if i ≤ r: start k = min(r-i+1, d1[mirror])   // reuse the mirror 4 expand k by explicit comparisons; push [l,r] right if it grows
1 / 1
03

Check

Three questions. Pick an answer to see why.

Q1

What is d1 for "aaa"?

Q2

The rightmost palindrome is [l, r] = [2, 10], i = 8 and d1[4] = 5. What is the starting radius k for i = 8?

Q3

Why is Manacher O(n) and not O(n²)?

04

Practice

Real problems to lock it in, easiest first.

LeetCodeLongest Palindromic Substring intermediate↗LeetCodePalindromic Substrings intermediate↗CSESLongest Palindrome intermediate↗CSESAll Palindromes advanced↗