Manacher's Algorithm, in depth: all longest palindromes by centre in linear time, the mirror argument, a full trace, and O(1) palindrome queries

The problem and the quadratic baseline

The brute-force approach checks every substring: O(n squared) substrings, O(n) to test each, O(n cubed) total. The standard improvement is to expand around each centre. Every palindrome has a centre, either a character (odd length) or the gap between two characters (even length), so there are 2n - 1 centres. From each, grow outwards while the characters match.

def longest_by_expansion(s):
    best = (0, 0)                        # half-open [lo, hi)
    for centre in range(2 * len(s) - 1):
        lo, hi = centre // 2, (centre + 1) // 2
        while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
            lo -= 1
            hi += 1
        if hi - lo - 1 > best[1] - best[0]:
            best = (lo + 1, hi)
    return s[best[0]:best[1]]

This is O(n squared) in the worst case, for example on a string of one repeated character, where nearly every centre expands almost to the ends. It is fine for short inputs and is a good brute-force oracle for testing. The waste is obvious on that worst case: after expanding around the middle you already know the whole string is symmetric, yet every later centre re-discovers by comparison what the symmetry already told you. Manacher's algorithm reuses that knowledge.

One kind of centre: the separator transform

Handling odd and even centres separately doubles the bookkeeping. The usual trick is to insert a separator between every pair of characters and at both ends. For s = "abaab" the transformed sequence is t = # a # b # a # a # b #, of length 2n + 1. Every palindrome in s, odd or even, now corresponds to an odd-length palindrome in t centred on a single index: characters of s sit at odd indices, gaps at even ones.

Define p[i] as the radius of the longest palindrome in t centred at i, not counting the centre itself. Because the separators pad both sides, p[i] is exactly the length of the corresponding palindrome in s. That identity is the reason for the transform, and it removes most off-by-one errors.

A detail most write-ups skip: the separator does not need to be a character absent from the input. Two positions compared during expansion are i - k and i + k, which differ by 2k and so have the same parity. Separators are only ever compared with separators and real characters with real characters. The implementation below uses None as the separator anyway, so the question never arises. Sentinel characters such as ^ and $ at the ends, a common variant that avoids bounds checks, do need to be absent from the input, so the version here uses explicit bounds checks instead.

The mirror argument

Scan i from left to right and remember the palindrome found so far whose right edge reaches furthest: centre c, right edge r = c + p[c]. Suppose i is inside it, so i is less than r. Its mirror image about c is j = 2c - i, which is to the left and whose radius is already known. Within the big palindrome, the neighbourhood of i is the reversal of the neighbourhood of j, so the palindrome around j also appears around i, as long as it stays inside the big palindrome.

That gives three cases. If the palindrome at j lies strictly inside the big one, p[i] = p[j] exactly, with no comparisons. If it reaches or passes the left edge, we only know that p[i] is at least r - i, because beyond r the symmetry says nothing; we must compare characters past r. If i is at or beyond r, we know nothing and expand from zero. All three collapse into one line: start from min(r - i, p[j]) when i is inside, zero otherwise, then try to expand.

The algorithm and why it is linear

def manacher(s):
    """p[i] = length of the longest palindrome in s centred at index i
    of t, where t = [sep, s[0], sep, s[1], ..., s[-1], sep]."""
    t = [None]
    for ch in s:
        t += [ch, None]
    n = len(t)
    p = [0] * n
    c = r = 0                          # rightmost palindrome: centre, right edge
    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

Why is this linear? Look at the inner loop. If the starting value came from the first case, the very first comparison fails, because the mirror's palindrome stopped where it did for a reason that the symmetry transfers to i. Otherwise the starting radius places i + p[i] at r or beyond, and every successful comparison pushes i + p[i] further right, after which r is updated to it. So every successful comparison increases r by one, r never decreases and never exceeds n - 1, and each i has at most one failed comparison. On t, which has 2n + 1 positions, that is at most about 2n successful comparisons plus one failure per index, roughly 4n in total, so O(n) in the length of s.

Worked example: abaab

Run it on "abaab", whose transformed form has eleven positions. The table records, for each index, where the starting radius came from and the result.

The final array is [0, 1, 0, 3, 0, 1, 4, 1, 0, 1, 0]. The maximum, 4, is at index 6, an even centre between the two a characters: the palindrome is baab, starting in s at (6 - 4) // 2 = 1. Index 3 records aba with length 3. Notice rows 7 to 10: once the palindrome centred at 6 reached the end, every later position copied or capped its radius from the mirror and did at most one comparison, which is the linear-time argument in action.

Reading answers out of the radius array

Everything useful is a short formula over p. The index mapping is the part people get wrong, so keep these together and test them.

def longest_palindrome(s):
    p = manacher(s)
    i = max(range(len(p)), key=p.__getitem__)
    start = (i - p[i]) // 2            # map t-index back to s
    return s[start:start + p[i]]

def count_palindromic_substrings(s):
    # a palindrome of length L at one centre contains (L + 1) // 2
    # shorter palindromes with the same centre, including itself
    return sum((x + 1) // 2 for x in manacher(s))

def palindrome_checker(s):
    p = manacher(s)
    def is_pal(lo, hi):                # half-open, non-empty slice s[lo:hi]
        return p[lo + hi] >= hi - lo   # its centre in t is index lo + hi
    return is_pal

The checker is the most reusable piece. The slice s[lo:hi] has its centre in t at index lo + hi (odd slices centre on a character at an odd index, even slices on a gap at an even one), and it is a palindrome exactly when the palindrome at that centre is at least as long as the slice. After O(n) preprocessing, every palindrome test is O(1). That turns the O(n cubed) naive version of minimum palindrome partitioning into an O(n squared) dynamic program with no separate palindrome table, and it is the standard way to build such tables in problems from dynamic programming.

If you prefer two arrays without the transform, the common d1/d2 formulation is the same information: for original index k, the number of odd palindromes centred there is (p[2k + 1] + 1) // 2 and the number of even palindromes centred on the gap before it is p[2k] // 2.

Alternatives, trade-offs and pitfalls

Manacher is not the only tool here, and knowing the alternatives tells you when to reach for it.

Like the prefix function in KMP and the LCP array described in the Kasai LCP article, Manacher gets linear time by reusing earlier work and proving that a pointer only moves forward; once you see that pattern you will find it in many string algorithms.

Practical pitfalls: decide what a character is before you start, because Python strings index code points, UTF-8 byte arrays index bytes, and neither matches what users see for accents built from combining marks or emoji sequences; normalise first if palindromes are about visible text. Decide whether case and punctuation count, and if you filter them out, keep a map from filtered positions back to the original so you can report the right slice. For very long inputs in Python, the list-of-integers array costs several times the input size in memory; array('i') or NumPy reduces it, and the per-character loop is the bottleneck, so consider a compiled implementation above a few million characters.

What to do next

1. Type out manacher from memory, then test it against longest_by_expansion on thousands of random strings over a two-letter alphabet, where palindromes are dense.
2. Trace the algorithm by hand on "aaaa" and confirm that every comparison after the first few extends r.
3. Implement the O(1) is_pal(lo, hi) check and use it to solve minimum palindrome partitioning in O(n squared).
4. Count palindromic substrings with the (p + 1) // 2 formula and verify it against brute force.
5. Rewrite the function using d1 and d2 arrays and check they agree with the transformed version.
6. Decide your character model (code points, bytes, normalised text) for any real-world input before you ship.