Manacher’s Algorithm

Finding Every Palindrome Without Checking Every Substring

8 min readOct 13, 2026

Intro

No doubt that the daily usage of the AI tools for shipping has a long-term effects on the way we think, the depth of critical thinking and approaches your brain recommend to solve the problem.

One solution I’ve tried the last times to made a weekly habit to solve advanced problems, not with one solution but different and without using any of the AI tools. During this, I’ve been exposed to the Manacher’s algorithm to solve the longest palindrome substring.

You should know that the brute force solution takes O(n³) time complexity while dynamic programming technique (DP) solved in O(n²) and hashing used with the binary search technique solved it in O(n log n). Manacher’s algorithm solved the problem in O(n), be curious and let’s see the beauty of this algorithm, continue . . .

This time the image comes from my humble camera and somehow it fits with the concept :D

Manacher’s Algorithm

A palindrome string is read the same forward and backward: racecar, level, and even a single character such as a is considered a palindrome.

Finding the longest palindromic substring sounds straightforward. Simply, pick a starting position, expand the substring, and check whether it is a palindrome. Repeat for every possible starting position.

The problem is that there are O(n²) possible substrings in a string of length (n). And checking each one can make the total work O(n³). Even the better expand-around-center solution takes O(n²) time in the worst case.

Manacher’s algorithm solves the problem in O(n) time complexity, its trick is not to avoid expanding palindromes altogether but to avoid repeating expansions whose answers can be inferred from palindromes we have already explored.

We will build that idea from the ground up, using abacaba as our running example. After this in the resources, you can find attached an amazing website that visualize each step in the algorithm, you can play with it, troubleshoot and absorb the idea better, continue . . .

1. First, what exactly are we looking for?

A substring is a contiguous part of a string. In abacaba, bacab is a substring, but baa is not.

A substring is palindromic when its characters match symmetrically around a center:

a b a c a b a
      ^
    center

The center can be a character, as in aba, or a gap between two characters, as in abba. In other words, the even-length palindromes do not have a single middle character.

Our goal is to find the longest palindromic substring. Manacher’s algorithm can also calculate the palindrome radius at every center, which means it reveals all palindromic substrings’ maximum extents, not just the longest one.

2. The simple approach: expand around every center

Every palindrome has a center. So instead of checking every possible substring, we can try each character as a center and expand outward while the two sides match.

For odd-length palindromes, start with one character:

a b a c a
    ^
    c

For even-length palindromes, start with the gap between two characters:

a b b a
  ^ ^
  center is the gap

For each center, compare the characters immediately to its left and right. If they match, expand again. Stop at the first mismatch or when the string boundary is reached.

This is already a major improvement over checking every substring. There are O(n) centers, and a single expansion can take O(n) time, so the worst-case complexity is O(n²).

The remaining question is: Can we use a palindrome we already know to avoid expanding from scratch at the next center?

That is the key to Manacher’s algorithm, continue I promise you’ll enjoy the core of this algorithm, it literally the deceptively simple (السهل الممتنع)

3. Guess what: the palindromes contain reusable information

Suppose we have already found a large palindrome. Because it reads the same forward and backward, the section on its left mirrors the section on its right, congratulations you almost got it . . .

For example, in abacaba, the whole string is a palindrome centered at index 3:

  Index: 0 1 2 3  4 5 6
 String: a b a c  a b a
         └─────┬────┘
               3

Focus please, the characters at equal distances from index 3 are equal:

- index 2 mirrors index 4: a and a
- index 1 mirrors index 5: b and b
- index 0 mirrors index 6: a and a

If we are processing a center inside this known palindrome, we may already know part of its radius by looking at the corresponding mirrored center on the other side.

That means we do not always need to compare characters one by one but we can reuse the radius information from the mirror.

There is one important limitation: mirroring is useful only within the boundaries of the palindrome. Beyond those boundaries, we do not know whether the characters will match. We must compare them directly, but still a progress.

4. The two pieces of state

Manacher’s algorithm processes centers from left to right while maintaining mainly two values:

- C (center): the center of the palindrome that currently reaches farthest to the right.
- R (the right boundary): the rightmost index covered by that palindrome.

For a current center i, its mirrored center inside the palindrome can be simply calculated by:

Why?
The center is the midpoint between mirror and i, so
C = (mirror + i) / 2, rearranging gives us mirror = 2C - i.

Okey? Now the algorithm stores a radius array P. In the transformed string introduced next, P[i] is the number of positions we can expand from i while preserving the palindrome.

Now the issue appears: do we need different paths of executions, one for odd length and another for even?

Get Mohamed Hassan’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

We will use a transformed string to make odd and even palindromes behave uniformly, continue . . .

5. One transformation handles odd and even palindromes

A common implementation inserts a separator between characters and at both ends. For example:

Original: a b b a
Transformed: # a # b # b # a #

Now every palindrome in the original string corresponds to an odd-length palindrome in the transformed string.

The even palindrome abba becomes #a#b#b#a#, centered on a separator.

We also add distinct sentinels to the ends to simplify boundary checks. One convenient representation is:

Original: a b a c a b a
Transformed: ^ # a # b # a # c # a  #  b  #  a  #  $
Index:       0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Here ^ and $ are sentinels that do not appear in the input. # must also be a separator that cannot occur in the input, or the implementation must escape or otherwise handle collisions. With these assumptions, expansion can compare neighboring characters without separately checking the string boundaries.

In this representation, P[i] is the number of successful expansions from transformed index i. The original palindrome length is exactly P[i], and its original start index is:

For example, the original palindrome aba centered at original index 2 has transformed center 5 and radius 3, so its length is 3 and its start is
(5 - 3) / 2 = 1.

6. The algorithm: one center at a time

At each transformed index i, do the following:

1. If i is inside the current rightmost palindrome (i < R ), use its mirrored center to initialize P[i] because simply the radius cannot extend beyond the known right boundary, so initialize it to the smaller of the mirrored radius and R - i, here, we take the benefit from the already calculated info about the palindrome before, this is the core of this algorithm.

2. Expand while the characters immediately outside the current radius match.

3. If this palindrome reaches farther right than the previous rightmost palindrome, update C and R.

4. Continue to the next center.

The initialization is the clever part:

This says: if we are outside the known palindrome, start with no known radius. If we are inside it, reuse as much of the mirrored radius as we can safely prove.

Notice what the algorithm does not do: it does not blindly copy the mirrored radius. The min() operation is essential because the mirrored palindrome might extend beyond the boundary that has already been verified.

7. A concrete example: why the mirror saves work

Consider the original string abacaba, so its transformed version is:

Index:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
input:  ^ # a # b # a # c #  a  #  b  #  a  #  $
P arr:    0 1 0 3 0 1 0 7 0  1  0  3  0  1  0

The center at transformed index 8 is the c. Expanding from it reveals the whole palindrome, reaching from index 1 to index 15. Therefore C = 8 and R = 15.

Now consider transformed index 12, which is the b on the right side. Its mirror around C = 8 is: 4

mirror = 2(8) - 12 = 4

Index 4 is also a b. The radius at that mirrored index is already known. Since index 12 is inside the right boundary, we can initialize its radius using that mirrored value, capped at R - 12.

The mirrored information gives us a safe starting point, not necessarily the final answer. If expansion reaches beyond R, we must compare those new characters directly. The known palindrome cannot tell us what lies outside itself.

This distinction is what keeps the algorithm both fast and correct.

8. Why is it linear instead of quadratic?

At first glance, the while loop looks expensive. It can expand many times for a single center, so why is the total time O(n)?

The answer is the right boundary.
Focus please: whenever expansion compares characters beyond the current right boundary and succeeds, the right boundary moves farther to the right. Across the entire algorithm, that boundary can only move forward through the transformed string. It cannot move backward, as simple as that.

Most work inside the known boundary is avoided through mirrored radii. The successful comparisons that extend the boundary can happen only a linear number of times. Each center is also processed once.
This is why the total time is O(n), and the radius array uses O(n) space.

In my opionion, the important lesson is not that every individual center takes constant time. Some centers can still trigger several comparisons. The linear bound comes from the fact that successful comparisons that discover new territory advance a shared boundary, rather than repeatedly exploring the same territory from scratch.

9. The mental model to keep

Manacher’s algorithm is easiest to remember as three connected ideas:

1. Every palindrome has a center, so represent the problem using radii.

2. A known palindrome has symmetry, so reuse the radius of a mirrored center.

3. Symmetry is only guaranteed inside the known right boundary, so pick the reused radius and expand when necessary.

The algorithm is not magic, and it does not somehow know future characters, it simply uses what has already been proven to avoid repeating work. That is why it can find the longest palindromic substring in linear time.

Crux to remember: when a problem has symmetry, ask if the work done on one side can tell you something about the other. Manacher’s algorithm turns that question into a precise linear-time solution.