Manacher's Algorithm

Finding all palindromic substrings, and the longest palindrome, in linear time by reusing mirror symmetry.

The palindrome problem

Manacher's algorithm computes, for every center in a string, the radius of the longest palindrome centered there, in O(n) total. A brute-force expand-around-center approach is O(n^2); Manacher reuses palindrome symmetry to avoid re-expanding regions already known to be palindromic.

Unifying odd and even

Kronos motion — confinement time

To handle both odd- and even-length palindromes uniformly, the string is transformed by inserting a separator (such as #) between every character and at the ends. Every palindrome in the transformed string has odd length, so a single radius array captures all cases; a radius in the transformed string maps directly back to a length in the original.

Reusing the mirror

The algorithm tracks the rightmost palindrome found so far, with center c and right edge r. For a position i inside that palindrome, its mirror position 2c - i gives a lower bound on i's radius for free; only expansion beyond r requires new character comparisons. Because r only moves right, total comparison work is linear.

Core loop

python

def manacher(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t); p = [0]*n; c = r = 0
    for i in range(n):
        if i < r:
            p[i] = min(r - i, p[2*c - i])
        while i-p[i]-1 >= 0 and i+p[i]+1 < n and t[i-p[i]-1] == t[i+p[i]+1]:
            p[i] += 1
        if i + p[i] > r:
            c, r = i, i + p[i]
    return p

Uses

Longest palindromic substring in linear time.
Counting all palindromic substrings.
Palindromic factorization and related string dynamic programs.
A companion to the Z-algorithm in the toolkit of linear string methods.