Introduction

Manacher’s algorithm finds the longest palindromic substring in linear time. Its power comes from reusing information about previously discovered palindromes instead of expanding from every center independently.

Why the Naive Approach Is Slower

A straightforward solution checks each character, or each gap between characters, as a palindrome center and expands outward. That works, but the worst-case runtime is quadratic.

Manacher’s algorithm avoids repeated work by exploiting symmetry. Once you know a palindrome around one center, you can infer partial information about mirrored positions inside it.

Preprocessing the String

The algorithm first transforms the string so odd-length and even-length palindromes can be handled uniformly. A common trick is to insert separators.

For example, the string abba becomes:

^#a#b#b#a#$

The sentinels at the ends simplify boundary checks, and the separators make every palindrome effectively centered on one position in the transformed string.

The Core Arrays and Pointers

Manacher’s algorithm keeps:

• 'P[i]: palindrome radius around position i in the transformed string'
• 'center: the center of the rightmost palindrome found so far'
• 'right: the right boundary of that palindrome'

For each position i, it computes the mirror position around center:

• 'mirror = 2 * center - i'

If i is inside the current right boundary, the mirrored radius gives a starting point for P[i]. Then the algorithm expands only as much as necessary.

Python Implementation

1def longest_palindrome(s: str) -> str:
2    if not s:
3        return ""
4
5    t = "^#" + "#".join(s) + "#$"
6    p = [0] * len(t)
7    center = 0
8    right = 0
9
10    for i in range(1, len(t) - 1):
11        mirror = 2 * center - i
12
13        if i < right:
14            p[i] = min(right - i, p[mirror])
15
16        while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
17            p[i] += 1
18
19        if i + p[i] > right:
20            center = i
21            right = i + p[i]
22
23    max_len = max(p)
24    center_index = p.index(max_len)
25    start = (center_index - max_len) // 2
26    return s[start:start + max_len]
27
28
29print(longest_palindrome("babad"))
30print(longest_palindrome("cbbd"))

This runs in O(n) time because each expansion contributes to moving the right boundary forward rather than redoing the same comparisons from scratch.

Why the Mirror Trick Works

Suppose you already know a palindrome centered at center reaching to right. If a new position i lies inside that span, its mirror on the other side of the center has already been analyzed.

That means:

• some of the radius at i is already known
• only the part near the boundary may need fresh expansion

This is the reason Manacher’s algorithm stays linear. It does not fully restart expansion from every position.

Recovering the Answer in the Original String

The algorithm works on the transformed string, but the final answer must be mapped back to the original string. The formula:

• 'start = (center_index - max_len) // 2'

converts the transformed center and radius into the original substring start index.

That mapping is easy to get wrong if you do not keep track of how separators change the index layout.

When to Use It

Manacher’s algorithm is excellent when:

• you need the longest palindromic substring exactly
• input strings can be large
• asymptotic performance matters

If clarity matters more than optimal asymptotic complexity and inputs are small, center expansion is often easier to explain and maintain.

Common Pitfalls

The biggest mistake is misunderstanding what P[i] stores. It is the radius in the transformed string, not the substring length in the original string.

Another issue is preprocessing incorrectly. Missing separators or sentinels makes boundary handling and even-length palindromes much harder.

Developers also often get the final index conversion wrong when mapping from the transformed string back to the original string.

Finally, do not use Manacher’s algorithm just because it is clever. If input sizes are small, a simpler O(n^2) center-expansion approach may be the better engineering choice.

Summary

• Manacher’s algorithm finds the longest palindromic substring in linear time.
• It works by preprocessing the string and reusing mirrored palindrome information.
• 'P[i], center, and right are the key state variables.'
• The transformed-string index mapping must be handled carefully.
• Use it when performance matters; otherwise, simpler palindrome expansion may be sufficient.