cf.completefrontend
STRING ALGORITHMS · ADVANCED

Manacher's algorithm

Find the longest palindrome around every center in linear time by reusing mirror images inside a palindrome already found.

Time O(n)Space O(n)3 practice problemsStep-through picture

The idea

Expanding around every center finds palindromes in O(n^2) time. Manacher's algorithm gets the same answers in O(n) time. It is named after Glenn Manacher, who published it in 1975.

The trick is a mirror. Suppose you already know a long palindrome. Its left half is the mirror image of its right half. So a palindrome centered on the left side has a twin centered on the right side, at least up to the edge of the big palindrome. You can copy that size for free and only grow past the edge.

To treat odd and even palindromes the same way, the algorithm first puts a # between every two letters and at both ends: abba becomes #a#b#b#a#. Now every palindrome has a single middle character. For each position it stores radius[i]: how far the palindrome around i reaches. That number is also the length of the matching palindrome in the original text.

An everyday example

Reading a symmetric building

You walk along a long building and note how far the symmetry reaches around each window. Once you find a big symmetric front, its left half is a mirror of its right half. When you reach a window on the right half, you don't measure from scratch. You look at its mirror window on the left half, which you already measured, and copy that number. You only walk further when the copied symmetry touches the edge of the big front, because beyond that edge you don't know anything yet.

How the example maps to the code
In the exampleIn the code
The big symmetric front you know aboutThe palindrome from 2 * center - right to right
The window you stand atPosition i in t
Its mirror window on the left half2 * center - i
Copying the mirror's number, capped at the edgeMath.min(right - i, radius[2 * center - i])
Measuring past the edgeThe while loop that grows radius[i]

From the slow way to manacher's algorithm

  1. Expanding around every center costs O(n^2) on text like aaaaaaaa, because each center compares letters that earlier centers already compared. To get faster, you must never compare letters when the answer is already known.
  2. Here is what a known palindrome already tells you. If the text from center - r to center + r is a palindrome, its right half is the mirror image of its left half. So the palindrome around a position i on the right side looks exactly like the one around its mirror, 2 * center - i, as long as both stay inside the big palindrome.
  3. That means radius[i] can start at the mirror's radius instead of at 0. There's one limit: the copy is only proven up to the big palindrome's edge, right. So start at Math.min(right - i, radius[2 * center - i]), and grow past the edge with ordinary comparisons.
  4. Odd and even palindromes would need two copies of all this, so first put # between all letters and at both ends. Then every palindrome in t has a single middle character. Walk i from left to right, copy from the mirror, grow, and whenever a palindrome reaches past right, make it the new center and right. That loop is Manacher's algorithm.

How it works

  1. Build t by putting # around every character, so aba becomes #a#b#a#. Now every palindrome in t has a single middle.
  2. Make radius, filled with 0. radius[i] will be how many characters the palindrome around i reaches on each side.
  3. Keep center and right: the palindrome found so far that reaches furthest right, and the index where it ends.
  4. For each i, if i < right, start radius[i] at its mirror's value radius[2 * center - i], but no more than right - i, the room left before the edge.
  5. Grow radius[i] while the characters just outside it on both sides are equal.
  6. If the palindrome around i now reaches past right, it becomes the new center and right.
  7. At the end, radius[i] is the length of the palindrome in the original text centered there. The biggest value is the longest palindrome.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function manacher(text) {
  2. const t = "#" + text.split("").join("#") + "#";
  3. const radius = new Array(t.length).fill(0);
  4. let center = 0;
  5. let right = 0;
  6. for (let i = 0; i < t.length; i++) {
  7. if (i < right) {
  8. radius[i] = Math.min(right - i, radius[2 * center - i]);
  9. }
  10. while (
  11. i - radius[i] - 1 >= 0 &&
  12. i + radius[i] + 1 < t.length &&
  13. t[i - radius[i] - 1] === t[i + radius[i] + 1]
  14. ) {
  15. radius[i]++;
  16. }
  17. if (i + radius[i] > right) {
  18. center = i;
  19. right = i + radius[i];
  20. }
  21. }
  22. return radius;
  23. }

How fast it is

TimeO(n)
Extra memoryO(n)

The edge right only moves right, so all the growing steps together are at most about 2n. The t string and radius array each hold about 2n items.

  • Best caseO(n)

    Text with no palindrome longer than one letter, like abcdef: almost nothing grows, and each position does O(1) work.

  • Average caseO(n)

    Any text: the total growth is limited by how far right can move.

  • Worst caseO(n)

    One letter repeated, like aaaaaaaa: big palindromes everywhere, but the while loop grows only 15 times for 8 letters, because each step pushes right forward.

Common mistakes

  • Copying the mirror's radius without the right - i cap. Past the edge the mirror proves nothing, and the result comes out too big.
  • Forgetting the # characters and handling even palindromes separately. It works but doubles the code and the chances of an off-by-one bug.
  • Looping over text.length when reading the result. radius has 2n + 1 entries, one per character of t, so scan all of t.length or you miss the palindromes on the right.
  • Converting back to the original index with i / 2 instead of (i - radius[i]) / 2. The first is the middle, not the start.

When to use it

Look for these clues in a problem:

  • You need the longest palindrome, or all palindromes, in text that can be 10^5 characters or more.
  • An O(n^2) expand-around-center solution is too slow for the given size.
  • You need the palindrome size at every center, not just one answer.
  • The problem counts palindromic substrings in very long text.

Check yourself

Answer each one in your head first, then open it.

What is t for noon, and where is the largest radius?

t is #n#o#o#n#, and the largest radius is 4, at the middle #, index 4. That matches noon, which has length 4.

Why is the copied value capped at right - i?

The mirror argument only covers letters inside the known palindrome. Past right, nothing has been compared yet, so the mirror's radius proves nothing there.

Why does a radius in t equal the palindrome's length in the original text?

A longest palindrome in t always starts and ends with an added #. Its 2r + 1 characters are r + 1 added # letters and r real letters.

At most how many times can the while loop grow a radius during the whole run?

About 2n + 1 times, the length of t. Each successful step moves right forward, and right never moves back.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Two rules hold at the top of each loop. First, every radius[j] for j < i is exact: the palindrome around j in t reaches exactly radius[j] steps each way. Second, center and right describe the palindrome found so far whose right end is furthest right. Both hold at the start, with nothing computed and right = 0.

The copy step is safe. Inside the palindrome around center, the text read to the left from i equals the text read to the right from the mirror 2 * center - i, and the other way round. So any palindrome around the mirror that stays inside the big one has a twin around i. Capping at right - i keeps only the part that's proven, and the while loop checks everything past that point with real comparisons, so radius[i] ends exact.

If the copied value is smaller than the room right - i, the very first check fails, because the mirror's palindrome also stopped there. So every successful growth step happens past right, and afterwards right moves to the new end. Since right only moves right and stops at the end of t, all growth steps together are at most t.length, which is 2n + 1. The loop is O(n), and when it ends every radius is exact.

Going deeper

3 more ideas

Why copying the mirror is safe

Inside the palindrome around center, the text at i looks exactly like the text at its mirror 2 * center - i, read backward. So any palindrome around the mirror that stays inside the big palindrome also exists around i. If the mirror's palindrome reaches the edge, only the part inside the edge is guaranteed, which is why the copied value is capped at right - i.

Why it is linear

Copying the mirror costs O(1). The while loop is the only part that can be slow, but every time it grows past right, right moves right afterwards, and right never moves left. It can only move right about 2n times in total, so all the growing together costs O(n). Growth that stays inside right stops at the first check, because the mirror already told us the answer.

Turning radii back into the original text

If radius[i] is the biggest value, the palindrome in the original text starts at (i - radius[i]) / 2 and has length radius[i]. For counting all palindromic substrings, the palindrome around i contains Math.ceil(radius[i] / 2) smaller palindromes with the same middle, so add those up.

Work it by hand

Every step in a table, with why

Find every palindrome radius in a 6-letter text. At index 11 of t, the mirror's radius is too big and must be capped.

text = "abacab", so t = "#a#b#a#c#a#b#"

Stepit[i]Start from mirrorradius[i]center, rightWhat happensWhy
10#-00, 0nothing to growIndex 0 has no left side, so radius[0] stays 0.
21a-11, 2grow 1: new box1 < right is false, so there's no mirror. t[0] and t[2] are both #, so it grows to 1. It reaches index 2, past right = 0, so it becomes the new box.
32#-01, 2no growth2 < 2 is false, so no mirror. t[1] is a and t[3] is b.
43b-33, 6grow 3: new boxThree pairs match, covering #a#b#a#, which is aba in the original text.
54#mirror 2: min(2, 0) = 003, 6copy 0Inside the box. The mirror of 4 around 3 is 2, which had radius 0. One check, b against a, fails.
65amirror 1: min(1, 1) = 113, 6copy 1The mirror had radius 1, and there is exactly 1 step of room. The next pair, t[3] and t[7], is b against c, so it stays 1.
76#-03, 6no growth6 < 6 is false, so the box doesn't help. a against c fails.
87c-57, 12grow 5: new boxFive pairs match, covering t[2] to t[12], which is bacab in the original text. The new box reaches index 12.
98#mirror 6: min(4, 0) = 007, 12copy 0The mirror had radius 0. One failed check.
109amirror 5: min(3, 1) = 117, 12copy 1The mirror had radius 1 with room to spare, so the answer is 1. One failed check, c against b.
1110#mirror 4: min(2, 0) = 007, 12copy 0One failed check.
1211bmirror 3: min(1, 3) = 117, 12capped at 1The mirror, index 3, had radius 3, but only 1 step of room is left before right = 12. The cap matters: the next step would need t[13], which doesn't exist.
1312#-07, 12at the end12 < 12 is false, and there's nothing to the right. The loop ends.

It returns [0, 1, 0, 3, 0, 1, 0, 5, 0, 1, 0, 1, 0]. The largest radius is 5 at i = 7, so the longest palindrome starts at (7 - 5) / 2 = 1 with length 5: bacab. The while loop grew only 9 times in total.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Manacher's algorithmO(n)O(n)Long texts, or many palindrome questions about one text: every center's radius in one pass.
Expand around the centerO(n^2)O(1)Short texts and most interviews: far simpler to write and explain.
Hashing with binary searchO(n log n)O(n)You already have prefix hashes of the text and its reverse. Binary search each center's radius; simpler to reason about, but hash collisions are possible.
Dynamic programming tableO(n^2)O(n^2)Small texts where you want a stored answer for every piece.

Extra memory: O(n): t has 2n + 1 characters and radius has 2n + 1 numbers.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Manacher's algorithm and the other approaches, on a scale where each line up is 10 times more steps.
  • Manacher's algorithm O(n)
  • Expand around the center, Dynamic programming table O(n^2)
  • Hashing with binary search O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Manacher's algorithm101,0001 million
Expand around the center1001 million1 trillion
Hashing with binary search339,96620 million
Dynamic programming table1001 million1 trillion

Inputs that need care

5 tricky inputs
Empty text: ""
t becomes ##, nothing grows, and it returns [0, 0]. The longest palindrome has length 0.
One letter: "z"
t is #z# and it returns [0, 1, 0]: a palindrome of length 1.
All the same letter: "aaaa"
It returns [0, 1, 2, 3, 4, 3, 2, 1, 0]. The middle # has radius 4, the whole text, which starts at (4 - 4) / 2 = 0.
Text that contains # itself: "a#b"
Still correct. The two positions compared always have the same parity, even or odd, so an added # is only ever compared with another added #. Any separator character works.
A very long text, like 1,000,000 characters
split("") first makes an array of a million strings, and t doubles the size. To save memory, skip t and read it on the fly: # when the index is even, and text[(k - 1) / 2] when k is odd.

Variations and follow-ups

Twists interviewers add

Is any piece a palindrome?

After one run, checking whether text.slice(l, r + 1) is a palindrome takes O(1). Its middle in t is at index l + r + 1, so check that radius[l + r + 1] >= r - l + 1.

Longest palindrome at the start

Look for the largest i where i - radius[i] === 0: that palindrome touches the start of t. Its radius is the length of the longest palindrome that starts at index 0, which gives the shortest text to add in front to make the whole thing a palindrome.

Counting all palindromes

The palindrome around i contains Math.ceil(radius[i] / 2) palindromes of the original text with the same middle. Adding that up over every i counts all palindromic pieces in O(n).

Two arrays instead of #

Some versions skip t and keep one array for odd palindromes and one for even ones. They use less memory but need two nearly identical loops, which is where off-by-one bugs hide.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when a palindrome question has a large limit, like n up to 10^6, where O(n^2) is too slow. For n up to a few thousand, expand around the center is enough, and interviewers usually prefer it.
  • Explain the mirror in one sentence: "inside a known palindrome, the right side repeats the left side backwards, so I copy the mirror's radius up to the edge, then grow". Then explain the # letters as a way to make every palindrome odd.
  • Be ready to argue O(n): every successful growth step moves right to the right, and right never moves back.
  • Test by hand: one letter, aaaa, and a case where the cap matters, like index 11 of t for abacab. The usual follow-up is reading the answer back: the start is (i - radius[i]) / 2 and the length is radius[i].

Where frontend code uses it

The same idea in real UI code
  • You rarely write Manacher's algorithm in UI code, but it shows a pattern you will use: reuse work you already did (here, the mirror) instead of recomputing it. React's memoization and incremental layout follow the same principle.
  • Text-analysis features that run in the browser on large pasted documents, such as finding repeated or mirrored sequences, need linear-time scans like this to stay responsive.

Related algorithms