Wait, What? A string can contain quadratically many palindromic substrings, yet the essential information about all of them can be computed in linear time.
That apparent contradiction is the reason Manacher’s algorithm is worth learning. The algorithm does not print every palindrome. Instead, for each possible center, it records the radius of the longest palindrome around that center. Shorter palindromes at the same center are then implied. The result is a compact representation computed in O(n).
Quick Read
One-sentence answer: Manacher’s algorithm finds the maximal palindrome around every center in linear time by reusing the radius of a center’s mirror inside the rightmost palindrome already known.
- Beginner: learn expand-around-center and the odd/even center problem.
- Intermediate: store a radius per center and understand mirrored centers.
- Advanced: maintain the rightmost palindrome boundary and derive the reuse rule.
- Professional: prove linear time, choose a representation, test boundary cases and decide whether Manacher is actually the right string tool.
1. Begin With the Naive Algorithm
For every character position, expand left and right while the characters match. Do the same for gaps between characters to capture even-length palindromes. This approach is simple and often perfectly adequate. Its worst case is O(n²), for example on a string made of one repeated character, because many centers expand over long distances.
Do not skip this version. Manacher’s algorithm only becomes understandable when you can identify exactly which comparisons the naive method repeats.
2. Represent a Palindrome by Center and Radius
For an odd-length palindrome centered at i, let dodd[i] record how many matching layers extend from the center. For an even-length palindrome centered between i−1 and i, let deven[i] record its radius. This is the representation used in the current 2026 cp-algorithms treatment of Manacher’s algorithm.
Why is one radius enough? If the longest palindrome at a center has radius 5, then radii 4, 3, 2 and 1 at the same center are automatically palindromes as well. We store the maximal extent, not every substring.
3. The Symmetry You Are Allowed to Reuse
Suppose we already know a palindrome whose center is c and whose right boundary is r. Consider a new position i that lies inside it. Its mirror across c is j = 2c − i. Because the big palindrome is symmetric, some of the palindrome radius already known at j must also exist around i.
The trap is assuming the entire mirrored radius is safe. It is only safe until the known right boundary. Therefore the initial radius at i is limited by the smaller of the mirrored radius and the distance from i to r.
After taking that guaranteed radius for free, the algorithm performs fresh character comparisons only beyond the known boundary.
4. Trace One Example Before Coding
Use the string abacaba. The center at index 3 expands to the full string. Now inspect positions inside this palindrome. A center on the right has a mirror on the left. Some of its radius is inherited immediately because the surrounding large palindrome guarantees equality. Only when the inherited palindrome reaches the current right boundary do we need to compare new characters.
On paper, draw c, r, i and mirror(i). If you cannot locate all four confidently, do not write the optimized loop yet.
5. The Core Invariant
At each step, maintain the palindrome with the farthest right endpoint found so far. The array entries before the current index are already final. When i lies outside the known rightmost palindrome, start with the trivial radius and expand. When i lies inside it, initialize from the mirrored center, clipped to the right boundary, then expand only if possible beyond r. If the new palindrome extends farther, update the center and right boundary.
This invariant is the heart of the algorithm. The code is only a compact translation of it.
6. Odd and Even Palindromes: Two Good Designs
There are two common implementation strategies.
- Two-array design: compute odd and even radii separately. The indexing is explicit and maps directly to the original string.
- Transformed-string design: insert separators such as # between characters so every palindrome becomes odd-length in the transformed string. A single radius array is then sufficient.
Both are valid. The two-array approach is often easier to reason about mathematically. The transformed-string approach can simplify a single implementation but introduces a mapping layer back to original indices. Professional code should choose whichever representation makes the surrounding task less error-prone.
7. Why the Running Time Is O(n)
The elegant proof focuses on the right boundary. Character comparisons that remain inside the current rightmost palindrome are mostly avoided through mirror reuse. Fresh successful comparisons happen when expansion pushes the right boundary farther right. That boundary can move from the start of the string to the end only O(n) times. Failed comparisons add at most constant overhead per center. The total work is therefore linear.
This is a reusable proof pattern: identify a monotone quantity—in this case the farthest right boundary—and charge expensive progress to changes in that quantity.
8. What the Radius Arrays Let You Answer
- Find the longest palindromic substring.
- Count palindromic substrings by summing radii appropriately.
- Test whether a specified substring is a palindrome after suitable preprocessing.
- Locate all maximal palindromes around centers.
- Feed palindrome information into higher-level string dynamic programs.
A 2026 paper in the Combinatorial Pattern Matching conference explicitly describes Manacher’s radius information as the standard O(n)-time representation of maximal palindromes and builds a more compact O(n)-bit representation on top of it. That is a useful reminder that a 1975 algorithm remains a foundation for current string-algorithm research.
9. Manacher Versus Other Palindrome Tools
Use expand-around-center when n is small or simplicity dominates. Use dynamic programming when the task naturally needs interval states for many other reasons. Use rolling hashes when palindrome equality is one part of a broader substring-comparison system and probabilistic collision risk is acceptable or double hashing is controlled. Use an eertree/palindromic tree when you need the structure of distinct palindromic substrings under incremental extension. Manacher is strongest when you need all center radii in a static string.
10. Common Failure States
- Using the mirror radius without clipping it at the current right boundary.
- Mixing inclusive and exclusive boundary conventions.
- Getting the even-palindrome center definition wrong by one index.
- Transforming the string with separators but mapping the final radius back incorrectly.
- Claiming O(n) because the loop is single-level while hiding repeated expansion that can still be quadratic.
- Returning only the longest palindrome when the calling problem needs every center radius.
11. A Testing Suite That Exposes Bugs
- Empty string and one-character string.
- Two equal characters and two unequal characters.
- All identical characters:
aaaaaa. - No long palindrome:
abcdef. - Odd maximum:
racecar. - Even maximum:
abccba. - Nested palindromes:
abacaba. - Repeated motifs where a mirror radius is clipped by the boundary.
For small random strings, compare the Manacher result against an O(n²) expand-around-center reference implementation. Differential testing is one of the safest ways to validate an optimized string algorithm.
12. Practice Ladder: Beginner to Professional
- Level 1: mark every odd and even center in a short string.
- Level 2: implement naive expand-around-center and record maximal radii.
- Level 3: trace c, r, i and mirror(i) on paper.
- Level 4: implement odd-radius Manacher only.
- Level 5: add the even-radius version or switch to a transformed representation.
- Level 6: prove the right boundary advances only O(n) times.
- Level 7: build a differential tester against the naive implementation.
- Level 8: design an API that exposes radius arrays cleanly to a larger string-processing system.
13. How to Learn It Without Memorising It
Predict what the naive expansion will do. Run the naive version. Identify repeated comparisons. Then introduce the mirror rule and ask which comparisons become unnecessary. Finally, write the optimized version from the invariant rather than copying a template. Programming-education research on PRIMM, self-explanation and subgoal-labelled worked examples supports this kind of staged movement from prediction and interpretation toward independent construction.
14. Learning Hall Boundary
This article owns the algorithmic mechanics and professional judgement around Manacher’s algorithm. It uses tracing, prediction and explanation as teaching methods but does not take over the canonical jobs of MindOS, Bolt or the Student/Studying Interface.
Sources and Further Reading
- Glenn K. Manacher, A New Linear-Time “On-Line” Algorithm for Finding the Smallest Initial Palindrome of a String, Journal of the ACM 22(3), 1975, DOI 10.1145/321892.321896.
- cp-algorithms, Manacher’s Algorithm — Finding all sub-palindromes in O(N), updated April 12, 2026.
- Compact Representation of Maximal Palindromes, CPM 2026, which explicitly builds on the O(n)-time maximal-palindrome representation associated with Manacher’s algorithm.
- Recent programming-education research on algorithm visualisation, worked examples and scaffolded self-explanation informs the teaching progression used here.
Professional rule: understand Manacher’s algorithm when you can derive the mirror initialization from symmetry, explain the boundary clipping, prove linear time using right-boundary progress, and verify your implementation against a slower reference.
eduKate Sengkang 