16.12 Manacher Algorithm

Problem

You need to find palindromic substrings efficiently.

Given:

forgeeksskeegfor

the longest palindromic substring is:

geeksskeeg

A brute-force solution checks every substring and tests whether it is a palindrome. There are O(n²) substrings, and each check may cost O(n), giving O(n³) time if implemented directly. Even a better expand-around-center approach still costs O(n²) in the worst case.

The challenge is to find all palindrome radii, and therefore the longest palindromic substring, in linear time.

Solution

Manacher's algorithm computes, for every center position, the radius of the longest palindrome centered there.

It reuses information from previously discovered palindromes. When a center lies inside a known palindrome, its mirror position gives a lower bound on the palindrome radius at the current center.

This is the same kind of idea seen in KMP, Z Algorithm, and suffix structures: do not repeat comparisons that previous work has already justified.

Odd and Even Palindromes

Palindromes have two possible centers.

Odd-length palindromes have a character at the center:

racecar
   ^

Even-length palindromes have a gap at the center:

abba
  ^

A direct implementation often computes two arrays:

odd[i]  = radius of longest odd palindrome centered at i
even[i] = radius of longest even palindrome centered between i-1 and i

For example:

ababa

Odd radii:

Index	Center	Longest odd palindrome	Radius
0	a	a	1
1	b	aba	2
2	a	ababa	3
3	b	aba	2
4	a	a	1

The largest radius is 3, producing length:

2 * 3 - 1 = 5

The Mirror Idea

Suppose we already know a palindrome:

a b a b a
0 1 2 3 4

centered at index 2, spanning from 0 to 4.

Now consider index 3. Its mirror around center 2 is index 1.

a b a b a
  ^   ^
  1   3

If the palindrome at index 1 has radius 2, then index 3 also inherits part of that radius, as long as it stays inside the known boundary.

Manacher's algorithm maintains the rightmost palindrome currently known. For each new center, it uses the mirror center to initialize the radius, then expands only if necessary.

Maintaining the Right Boundary

At each step the algorithm keeps:

l = left boundary of the current rightmost palindrome
r = right boundary of the current rightmost palindrome

For center i, if i lies inside [l, r], then:

mirror = l + r - i

The current radius can start from:

min(previous_radius_at_mirror, r - i + 1)

Only comparisons beyond r are new.

This is the linear-time argument. The right boundary only moves to the right, and every expansion advances it at most once.

Odd Palindrome Algorithm

The odd-palindrome version computes radii centered on characters.

def manacherOdd
  (s : Array Char)
  : Array Nat :=
by
  -- Maintain the current rightmost odd palindrome.
  -- Use mirror centers to initialize each radius.
  -- Expand when the known boundary is reached.
  sorry

Pseudocode:

odd = array of zeros
l = 0
r = -1

for i in 0 .. n-1:
    if i > r:
        k = 1
    else:
        mirror = l + r - i
        k = min(odd[mirror], r - i + 1)

    while i-k >= 0 and i+k < n and s[i-k] == s[i+k]:
        k += 1

    odd[i] = k

    if i + k - 1 > r:
        l = i - k + 1
        r = i + k - 1

The radius includes the center character. A radius of 1 means a single-character palindrome.

Even Palindrome Algorithm

The even-palindrome version computes radii centered between characters.

def manacherEven
  (s : Array Char)
  : Array Nat :=
by
  -- Maintain the current rightmost even palindrome.
  -- Use mirrored gap centers.
  sorry

Pseudocode:

even = array of zeros
l = 0
r = -1

for i in 0 .. n-1:
    if i > r:
        k = 0
    else:
        mirror = l + r - i + 1
        k = min(even[mirror], r - i + 1)

    while i-k-1 >= 0 and i+k < n and s[i-k-1] == s[i+k]:
        k += 1

    even[i] = k

    if i + k - 1 > r:
        l = i - k
        r = i + k - 1

A radius of 0 means no nonempty even palindrome at that center.

Example

For:

abba

Odd radii:

[1, 1, 1, 1]

Even radii:

[0, 0, 2, 0]

The even radius at index 2 corresponds to:

abba

centered between positions 1 and 2.

The length is:

2 * 2 = 4

Recovering the Longest Palindrome

After computing both arrays, scan them.

For odd radius k at center i:

length = 2k - 1
start  = i - k + 1

For even radius k at center i:

length = 2k
start  = i - k

Keep the maximum length.

For:

forgeeksskeegfor

the maximum comes from an even center and yields:

geeksskeeg

Why It Is Linear

The expansion loops look suspicious because they are nested inside a loop over centers.

The key point is that expansions only compare characters beyond the current known right boundary. Each successful expansion moves that boundary to the right. Since the boundary cannot move past the end of the string, the total number of successful expansions is O(n).

The failed comparisons also occur once per center.

Therefore the total runtime is:

O(n)

Complexity Analysis

Let n be the length of the string.

Operation	Complexity
Odd radii	O(n)
Even radii	O(n)
Longest palindrome recovery	O(n)
Total	O(n)
Storage	O(n)

Manacher vs Eertree

Feature	Manacher	Eertree
Finds longest palindromic substring	Yes	Yes
Computes palindrome radius at every center	Yes	Indirect
Stores distinct palindromes	No	Yes
Counts distinct palindromes	No	Yes
Occurrence counting	Limited	Natural
Construction	O(n)	O(n)
Implementation difficulty	Moderate	Higher

Use Manacher when you need palindrome lengths or the longest palindrome.

Use an Eertree when you need the set of distinct palindromes or occurrence statistics.

Correctness

For each center, the algorithm initializes the radius using the mirror center when possible. The copied radius is valid because both centers lie inside a larger palindrome, so their internal characters correspond symmetrically.

If the copied radius reaches the current right boundary, the algorithm expands explicitly and verifies each additional character pair.

Thus each stored radius is neither too small nor too large. It contains all characters that can be justified by symmetry plus every additional matching pair found by direct comparison. The result is the exact maximum palindrome radius for every center.

Common Pitfalls

Do not mix the odd and even definitions. Odd radii include the center character; even radii count pairs around a gap.

Be careful with boundary arithmetic. Most bugs in Manacher's algorithm are off-by-one errors.

Do not use byte indexing blindly for Unicode text. A palindrome over bytes may differ from a palindrome over code points or grapheme clusters.

Remember that Manacher gives radii, not a list of distinct palindromes. Many radii may describe overlapping occurrences of the same palindrome.

Takeaway

Manacher's algorithm is the standard linear-time method for palindrome radii. It works by carrying forward symmetry information from the rightmost known palindrome and expanding only when new information is required. For longest-palindrome and all-center palindrome-radius problems, it is simpler and lighter than a palindromic tree while retaining optimal linear performance.