Manacher
Find the longest palindromic substring in linear time by reusing information from the rightmost known palindrome.
Interactive visualization
Use the controls to connect the idea to concrete operations before diving into the full write-up.
Palindrome radius
6
Palindromes around every center in linear time
Center on c in the transformed string; the palindrome expands symmetrically outward.
Family
Strings
Prefix-aware structures and text-centric search strategies.
Builds on
Foundational
You can start here without another page first.
Unlocks
0 next topics
Use these follow-ups when you want to apply the current idea in a richer setting.
Learning paths
2
This topic appears in curated progressions so you can keep moving without guessing the next step.
Problem
You want the longest palindromic substring, or the palindrome radius around every center.
A naive expand-around-center solution takes in the worst case. Manacher reduces that to linear time.
Core idea
Insert separators so even- and odd-length palindromes become one uniform case, then maintain the rightmost palindrome seen so far.
For a new center i inside that known palindrome, use its mirror position to get a guaranteed initial radius before doing any explicit comparisons.
That reuse is what kills the quadratic blowup.
Why it matters
Manacher is one of the classic “looks magical until you see the invariant” algorithms.
It teaches a powerful pattern:
once a symmetric region is known, interior positions can borrow information from mirrored positions
Complexity
| Operation | Time |
|---|---|
| All palindrome radii / longest palindromic substring |
Key takeaways
- Manacher is the linear-time answer to longest palindromic substring
- The transformed string removes the even/odd split
- The mirror trick reuses previously known palindrome coverage
- This is a rare string algorithm, but it belongs in a truly complete atlas
Practice problems
| Problem | Difficulty | Key idea |
|---|---|---|
| Longest Palindromic Substring | 🟡 Medium | Manacher or center expansion |
| Palindromic Substrings | 🟡 Medium | Count via radius information |
| Manacher references | 🔴 Hard | Full linear-time derivation |
Relation to other topics
- Z-Algorithm is another linear string routine based on reusing a rightmost interval
- Rabin-Karp can also test palindrome candidates, but through hashing instead of direct radius reuse
- Suffix Automaton is another advanced string structure for substring-heavy problems
Related directions
These topics live nearby conceptually, even if they are not direct prerequisites.
Rabin-Karp
Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.
Z-Algorithm
Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.
Suffix Automaton
Compress all substrings of a string into a linear-size automaton with suffix links.
More from Strings
Stay in the same family when you want parallel variations of the same mental model.
KMP (Knuth-Morris-Pratt)
Search for a pattern in linear time by reusing information about its own prefixes instead of restarting after mismatches.
Rabin-Karp
Search with rolling hashes so most windows can be rejected with arithmetic instead of full character comparisons.
Trie (Prefix Tree)
A tree-like data structure for efficient string storage and prefix-based retrieval. Essential for autocomplete, spell checking, and word search problems.
Z-Algorithm
Compute how much of the global prefix matches at every position, then reuse the active Z-box to stay linear.
Paths that include this topic
Follow one of these sequences if you want a guided next step instead of open-ended browsing.
String matching
Move from prefix reuse and rolling hashes to suffix-based indexing and automata.
Substring toolkit
Compare rolling hashes, sorted suffixes, automata, and palindrome-specific structure.
From the blog
Pair the atlas with recent writing from the rest of the site when you want a broader engineering perspective alongside the topic graph.