Manacher's algorithm: the longest palindrome in O(n)

The idea: grow palindromes from their centres, and reuse what is known

A palindrome reads the same both ways: abcbabcba, abaaba. Every palindrome has a centre, so one way to find the longest is to try every centre and expand while the characters on both sides are equal. That is expand around centre, and it costs O(n²) on a string like aaaaaaaa. Manacher's algorithm (1975) visits the centres in the same order but starts each expansion where the palindromes already found say it can, and finishes in O(n).

The # separators

An odd palindrome (aba) has a character in the middle, an even one (abba) has a gap. To treat both the same way, put a # between every two characters and at both ends: S of length n becomes S′ of length N = 2n + 1. Every palindrome of S is now an odd palindrome of S′, centred on a letter (odd length) or on a # (even length). Any character not in the string works; the #s only ever match each other.

For each centre i, P[i] is the radius: how many characters match on each side in S′. A palindrome of S′ always starts and ends with a #, so P[i] is exactly the palindrome's length in S, and it starts in S at (i − P[i]) / 2. The answer is read off the largest P. (Demo: even palindrome abaaba.)

The box: C and R

Manacher keeps one palindrome in hand: the one that reaches furthest right so far. Its centre is C and its right end is R = C + P[C]. On the canvas it is the blue bar above S′ and the blue line at R. When the expansion at a centre i ends further right (i + P[i] > R), that palindrome becomes the new box: C = i, R = i + P[i].

The mirror rule

Take the next centre i. If i < R it lies inside the box, and its mirror image around C is i′ = 2C − i, a centre that was handled earlier. The box reads the same both ways, so whatever surrounds i′ inside the box also surrounds i. P[i] therefore starts at

P[i] = min(R − i, P[i′])          if i < R
P[i] = 0                           otherwise

and then expands with ordinary compares. Three cases decide how much is left to do:

case	P[i]	why
P[i′] < R − i	= P[i′]	the palindrome at i′ stops inside the box, at a mismatch the mirror repeats at i
P[i′] > R − i	= R − i	the character just past R differs from its mirror inside the box, otherwise the box would have been longer
P[i′] = R − i	≥ R − i, expand	beyond R nothing is known yet

On babcbabcbaccba: centre 9 copies P[5] = 1 (first case); centre 11 copies P[3] = 3, which reaches R = 14 exactly, so it expands to 9 and becomes the new box (Demo: mirror and a new boundary); centre 15 sees P[7] = 7 but only R − i = 5 fits in the box, so P[15] = 5 (Demo: mirror capped at R). On abacabadabacaba the whole right half is copied from the left half.

Why it is linear

Count the compares. A compare that succeeds extends the palindrome at i past R (in the first two cases the first compare already fails), so every success moves R one place right. R only grows and never passes N − 1, so there are fewer than N successes in total. Each centre stops at most once with a failed compare, so fewer than N failures. That is under 2N = 4n + 2 compares: O(n). Expanding around every centre has no such bound: on aaaaaaaa every centre expands to the end of the string.

string	longest	Manacher compares	expand around centre
babcbabcbaccba (n = 14)	abcbabcba	45	59
abaaba (n = 6)	abaaba	16	22
aaaaaaaa (n = 8)	aaaaaaaa	15	64 = n²
abacabadabacaba (n = 15)	abacabadabacaba	48	71

Both columns count compares in S′, # against # included, and running off either end of S′ stops without a compare. (Demos: aaaaaaaa with Manacher, aaaaaaaa expanding every centre.)

Other ways to find palindromes

Expanding around centre is short to write and fine for short strings or strings with few repeats. A dynamic-programming table (is S[a..b] a palindrome?) is also O(n²) and needs O(n²) memory. Suffix structures and hashing solve it too: build a suffix array of S + a separator + reverse(S), or compare forward and backward rolling hashes with a binary search on the radius, in O(n log n). Manacher's idea, reusing what a previous match proved instead of comparing again, is the same one that makes KMP linear; there the failure table plays the part of the mirror.

What the page leaves out

The ^ and $ sentinels many implementations add so the loop needs no bounds check; the version without separators that keeps two arrays (odd and even radii); counting all palindromic substrings (the sum of ⌈P[i] / 2⌉); the palindromic tree (eertree), which lists every distinct palindrome; and online versions that add characters at the end.

References

Manacher, A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String (J. ACM, 1975)

Manacher's algorithm: finding all sub-palindromes in O(N) (cp-algorithms)

Longest palindromic substring (Wikipedia)