Manacher Palindrome Radii
Discover how mirror symmetry finds every palindrome radius and the longest palindromic substring.
By Riano · Published · Updated · Report a correction
Manacher's Algorithm
Mirror Symmetry in Palindromes
Manacher's algorithm computes every odd and even palindrome radius in linear time, compactly representing all palindrome occurrences. It achieves this by tracking a "window" of the rightmost identified palindrome and reusing previously calculated palindrome radii using mirror symmetry.
Finding the longest palindrome in "aabcbaa"
Consider finding all palindromes in the string "aabcbaa". We evaluate both odd-length (centered on a character) and even-length (centered between characters) palindromes by expanding out from each possible center.
Using exhaustive checking (without Manacher's window reuse), we find the following radii:
| Index | Char | Odd Radius | Even Radius |
|---|---|---|---|
| 0 | a | 1 | 0 |
| 1 | a | 1 | 1 |
| 2 | b | 1 | 0 |
| 3 | c | 4 | 0 |
| 4 | b | 1 | 0 |
| 5 | a | 1 | 0 |
| 6 | a | 1 | 1 |
- For index 3 ("c"), the odd radius expands to include "b"s (radius 2), "a"s (radius 3), and "a"s (radius 4). The palindrome is "aabcbaa".
- For index 1 ("a"), it shares an even-length center with index 0 ("a"), yielding an even radius of 1 for the palindrome "aa".
- The maximum length found across both arrays is 7, corresponding to the entire string starting at index 0 and ending at index 6.
Tracing the mirror
Open the Manacher Palindrome Radii explorer. Use the trace tools to see how mirror bounds reduce the number of character comparisons.
- Type
abacabain the Text input. - Click Step to step through the algorithm center by center. Observe how the odd-length array evaluates before the even-length array.
- When calculating the radius at index 5, notice how the algorithm uses the mirror index (index 1) across the main center (index 3). The known radius at index 1 is 2, so the initial bound for index 5 is 2 without comparing characters.
- Click Finish to skip to the end and observe the completed odd radii
[1, 2, 1, 4, 1, 2, 1]and longest length 7. - Click Reset to restart the tracing.
Limitations
Keep the following assumptions in mind:
- Alphabet: The explorer accepts only lowercase ASCII letters. The algorithm itself can work with any alphabet or character set, but complex graphemes or Unicode characters are not handled in this visualization.
- Memory: The core algorithm uses O(N) time and O(N) radius storage. This bounded teaching trace saves O(N) full-array frames, so its snapshot storage is O(N*N); it does not enumerate every substring.
- Length restriction: For UI layout constraints, the input length is limited to 12 characters.
References
The following external resource provides a comprehensive guide on the algorithm's structure and performance:
- Manacher's Algorithm - CP-Algorithms: Explains the odd/even definitions, mirror clipping, and right-boundary linearity logic.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Manacher Palindrome Radii module.
Try Manacher Palindrome Radii on Riano →