Manacher's Algorithm

Why Center Expansion Can Still Be Too Slow

A palindrome reads the same forward and backward, so the most direct longest-palindromic-substring solution expands around every center. That is already much better than checking every substring: it drops the brute-force O(n^3) idea to O(n^2). But on strings like aaaaaa...a, almost every center expands a long way, so the same equal-character relationships are rediscovered repeatedly.

Manacher's algorithm keeps the center-expansion intuition but stops paying for duplicate work. The key insight is symmetry. If a long palindrome centered at C is already known, then positions mirrored across C inherit information about how far their own palindromes must extend before any new checking is needed.

Normalizing Odd and Even Centers

Plain strings have two kinds of palindromes. racecar has an odd center on e; abba has an even center between the two bs. Manacher removes that split by inserting separators between every pair of characters and at both ends. For example, abba becomes #a#b#b#a#. Now every palindrome in the transformed string has a single center position, so one radius array can describe both odd and even cases.

original    : a b b a
transformed : # a # b # b # a #
index       : 0 1 2 3 4 5 6 7 8
radius P    : 0 1 0 1 4 1 0 1 0

The radius array P[i] stores how far the palindrome centered at i extends in the transformed string. A larger radius means more mirrored characters were confirmed on both sides. Once the transformed representation is in place, the problem becomes: compute all palindrome radii quickly.

Reusing Symmetry with Mirrors

Maintain the center C and right boundary R of the rightmost palindrome discovered so far. When you move to a new position i inside that palindrome, its mirror position is mirror = 2*C - i. Because the large palindrome around C is symmetric, P[mirror] tells you how much of P[i] is already guaranteed before any fresh comparison begins.

As with the Z algorithm, there are two cases. If the mirrored radius stays fully inside the current right boundary, you can copy it. If the mirrored radius would cross the boundary, you can only trust the part up to R - i, and then you resume expansion from there. The boundary acts like a certificate: everything inside it is already known to match by symmetry.

Known rightmost palindrome: center C = 4, right boundary R = 8
Now inspect i = 5
mirror = 2*C - i = 3
P[3] = 1 and R - i = 3
=> start P[5] at min(1, 3) = 1
=> no need to re-check the first symmetric layer around i
=> expand further only if positions beyond the inherited boundary match

Once every transformed center has a radius, the longest palindromic substring is the one with maximum P[i]. The original start index is (center - radius) / 2 when using the #a#b#...# transformation, and the original length equals radius. That mapping works because every real character is separated by exactly one #.

Go Implementation

The following implementation uses the # transformation because it keeps the index math simple enough to inspect. The algorithm builds the transformed string, computes the palindrome radii array, tracks the best center, and finally converts the winning transformed interval back into the original substring.

Practice Problems

Quiz

Summary

• Manacher starts from center expansion but removes repeated work through symmetry reuse.
• Separators unify odd and even palindromes into one transformed-string problem.
• Inside the rightmost known palindrome, mirrored centers inherit radius information for free.
• The radius array can answer more than just the single longest palindrome; it can also support counting and split-based palindrome problems.
• Most implementation bugs come from translation between transformed and original indices, so always verify that mapping carefully.