Manacher's Algorithm

Manacher's algorithm finds the longest palindromic substring in O(n) time. The brute-force "expand around every center" approach is O(n²); Manacher keeps that same expand-around-center idea but reuses already-computed radii through a mirror trick, so no character is examined more than a constant number of times.

For s = "aba" the transform is t = ^#a#b#a#$. The radius array ends up p = [0, 0, 1, 0, 3, 0, 1, 0, 0]; the maximum 3 sits at the center b, telling us the longest palindrome is "aba" with length 3.

Intuition

Expanding around every center is the obvious O(n²) method: pick a center, push outward while characters match. Two things make it slow. First, palindromes can be even-length ("abba"), which needs a separate "center between two characters" case. Second, neighboring centers redo each other's work.

The # transform kills the even/odd split: with separators, every palindrome of t is centered on a single character and is odd-length, so one radius array handles both. The mirror trick kills the redundant work: if center i lies inside the current rightmost palindrome (C, R), then by symmetry it looks just like its mirror 2*C - i — at least up to the boundary R. So we can copy p[mirror], clamped by how much room is left (R - i), and only try to expand beyond that. Each expansion either fails immediately or pushes R further right, and R only moves forward, so the total expansion work across the whole sweep is O(n).

Walk through it

Step through the animation on the right. The top row is t = ^#a#b#a#$. Pointer i is the center we are growing; mirror is its reflection across C; C and R (below the row) mark the rightmost palindrome so far. The live p array updates each step.

When i = 2 (the first a), it is outside R, so we start fresh and expand: #a# matches, giving p[2] = 1, and R jumps to 3. When i = 4 (the b), it expands the most — matching #a#b#a# outward to radius 3 — so C, R slide to 4, 7. Now watch i = 6 (the second a): it lies inside R = 7, so its mirror = 2 already proved a radius of 1. We seed p[6] = min(R - i, p[mirror]) = min(1, 1) = 1 for free and only attempt one more expansion (which fails at the sentinel). The biggest radius is p[4] = 3, so the answer is the length-3 palindrome "aba".

The code, line by line

def manacher(s):
    t = "^#" + "#".join(s) + "#$"
    p = [0] * len(t)
    c = r = 0
    for i in range(1, len(t) - 1):
        if i < r:
            mirror = 2 * c - i
            p[i] = min(r - i, p[mirror])
        else:
            p[i] = 0
        while 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 max(p)

• Line 2 builds t with # between characters and sentinels ^ / $ on the ends. The sentinels are distinct from everything else, so the while expansion stops at them automatically — no index bounds checks needed.
• p[i] is the radius of the palindrome centered at t[i]; in the transformed string this radius also equals the length of the original palindrome.
• Lines 6–8 are the mirror trick: when i is inside the rightmost palindrome, copy the mirror's radius but clamp it to r - i so it never claims more than R actually guarantees.
• Line 10 covers i at or beyond R — no mirror to lean on, so start at 0.
• Lines 11–12 expand: while the characters one step past each end match, grow the radius. The seed means we rarely start from 0, which is what saves the time.
• Lines 13–14 push C and R forward whenever the new palindrome reaches further right than any before — this is the only way R moves, and it only ever increases.
• Line 15 returns the largest radius; map i back to recover the substring itself.

Complexity

The while loop looks like it could make the whole thing quadratic, but every successful expansion advances R, and R spans 2n + 1 positions and never retreats. So across the entire outer loop the expansions do at most O(n) total work, and the sweep itself is O(n) — combined, O(n).

When to use / pitfalls

Practice