Finding Palindromic Substrings — Part 2: Manacher's Algorithm O(n)

Before reading this article, read Part 1: O(n³) and O(n²) solutions — it explains what a palindrome is, brute force, and center expansion in detail.

Where we left off in Part 1

In Part 1 we saw:

• O(n³) Brute Force: enumerate every substring and check if it's a palindrome — very slow
• O(n²) Center Expansion: treat each position as a center and expand both ways — much better, but still not enough

The core problem with center expansion: we throw away what we already learned.

Take "abacaba" — expanding from center 3 (c) we learn the whole string is a palindrome. Now we move to center 5 (a) and expand again from scratch! But center 5 sits inside the palindrome centered at 3 — can't we reuse that information?

That's exactly what Manacher's Algorithm does.

The core trick — track 3 things

As the algorithm runs, we keep 3 things in mind:

1. C (Center): the center of the palindrome that has reached furthest right so far
2. R (Right boundary): the right edge of that palindrome (exclusive — i.e. the palindrome extends up to R-1)
3. p[] array: the palindrome radius at each position (what we're computing)

s = ... [=====C=====R) ...
         ← palindrome →

What R means: from index 0 to R-1, somewhere we're inside a palindrome — and inside this range we can take a shortcut when processing a new position.

Now we process position i — two cases

Case 1: i >= R (outside the boundary)

s = ... [=====C=====R)  ...  i  ...
                              ↑
                    we're here now, outside R

We have no prior information about i. So there's no shortcut — expand trivially: match characters in both directions from i, and increment p[i] as long as they match.

When the expansion finishes, if i + p[i] > R, update C and R — because this new palindrome now reaches furthest right.

Case 2: i < R (inside the boundary) — here's the magic!

s = ... [  j  ===C===  i  )R ...
         ↑              ↑
       mirror        current

Since i lies inside the C-centered palindrome, there's a mirror image of i on the left side of C:

j = 2 * C - i

Why? C is the center of the palindrome. A palindrome is symmetric left to right. So however far i is to the right of C, j is that far to the left.

We already computed the palindrome radius p[j] at j. By the mirror property: inside the C-centered palindrome, the characters around i and the characters around j are identical (because the palindrome is symmetric)!

So can we just copy p[j] straight into p[i]? It depends! Three sub-cases:

Sub-case 2a: j's palindrome fits entirely inside (l, R)

s = ... [ (--j--)  C  (--i--) )R ...

j's palindrome doesn't touch the boundary — then symmetry guarantees i's palindrome is exactly the same.

→ p[i] = p[j] — no expansion needed! 🎉

Sub-case 2b: j's palindrome touches or extends past the left boundary (l)

s = (--j===[==  C  ==)i===???)R ...
        ↑ l                    ↑
  j's palindrome ran past the boundary

j's palindrome crosses the l boundary. Symmetry only guarantees things inside the (l, R) range — beyond it we don't know.

→ p[i] = R - i (take only what's guaranteed), then expand trivially past R — it might grow more, it might not.

Sub-case 2c: j's palindrome ends exactly at the boundary

This is just like 2b — start with p[i] = R - i and expand. Because symmetry can't tell us what's just outside the boundary.

Putting it all together — Pseudocode

for each position i:
    if i < R:
        j = 2 * C - i          // mirror position
        p[i] = min(p[j], R - i) // take only what's guaranteed

    // then expand (trivially)
    while s[i - p[i] - 1] == s[i + p[i] + 1]:
        p[i]++

    // boundary update
    if i + p[i] > R:
        C = i
        R = i + p[i]

Notice: min(p[j], R - i) — a single line handles all three sub-cases!

• p[j] < R - i → sub-case 2a (mirror copy, while loop won't run)
• p[j] >= R - i → sub-case 2b/2c (start expanding from R-i)

Why O(n)? — the complexity proof

This part matters. It might look O(n²) because of the while loop — but it isn't!

Key observation: each iteration of the while loop increases R by at least 1.

• R starts at 0
• R can go up to at most n
• R never decreases (only grows or stays the same)

So across the whole algorithm, the while loop runs at most n times total — averaging O(1) per position!

• everything else (mirror copy, boundary check) = O(1) per position
• n positions × O(1) = O(n) total!

Across all expansions, R grows at most n times → O(n)!

Detailed walkthrough — step by step

Take s = "abacaba". The transformed string is "#a#b#a#c#a#b#a#".

The algorithm starts with: C = 0, R = 0, p[] = [0, 0, 0, ...]

i = 1 ('a'): outside R, trivial expand → p[1] = 1 (palindrome: "a"). Update: C=1, R=2.

i = 3 ('b'): outside R, expand → p[3] = 1 (palindrome: "b"). Update: C=3, R=4.

i = 5 ('a'): outside R, expand → p[5] = 3 (palindrome: "#a#b#a#" = "aba"). Update: C=5, R=8.

i = 7 ('c'): i < R (7 < 8)! Mirror = 2×5 - 7 = 3, p[3] = 1. But i + p[mirror] = 7+1 = 8 = R, it touches the boundary! So start from p[7] = 1 and expand → p[7] = 7 (palindrome: "abacaba")! Update: C=7, R=14.

i = 9 ('a'): i < R, Mirror = 5, p[5] = 3. i + p[5] = 12 < R=14, fully inside → p[9] = p[5] = 3. No expansion needed! — this is the power of Manacher!

Interactive Simulation

In the simulation below, see for yourself how the algorithm works. Change the input, step through it:

Implementation — Odd-length

vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";   // sentinel characters
    vector<int> p(n + 2);
    int l = 0, r = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = min(r - i, p[l + (r - i)]);
        while (s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] > r) {
            l = i - p[i];
            r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}

Sentinel characters: we add $ at the start and ^ at the end so we don't need boundary checks. These two characters don't appear in the string, so the while loop stops on its own.

How do we handle even-length palindromes?

Instead of writing separate code for even-length palindromes, there's a trick — insert a # between every character of the string:

"abc" → "#a#b#c#"

Now every even-length palindrome becomes an odd-length palindrome centered on a #!

vector<int> manacher(string s) {
    string t;
    for (auto c : s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

Recovering the original info from the transformed array

From the result d[] of the transformed string:

• d[2*i] → even-length palindromes: d_even[i] = d[2*i] / 2
• d[2*i + 1] → odd-length palindromes: d_odd[i] = (d[2*i + 1] + 1) / 2

Time Complexity

O(n) — because r only grows, never shrinks. Total expansion across all positions = O(n).

Practice Problems

• Enumerate Palindromes — Library Checker
• Longest Palindrome — CSES
• Longest Palindrome Substring — LeetCode 5
• Palindromic Substrings — LeetCode 647
• Palindrome Degree — Codeforces 7D
• Palindrome Pairs — Codeforces 17E
• EPALIN — SPOJ

Summary

The full series