Manacher Palindrome Radii

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.

Tracing the mirror

Open the Manacher Palindrome Radii explorer. Use the trace tools to see how mirror bounds reduce the number of character comparisons.

1. Type abacaba in the Text input.
2. Click Step to step through the algorithm center by center. Observe how the odd-length array evaluates before the even-length array.
3. 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.
4. Click Finish to skip to the end and observe the completed odd radii [1, 2, 1, 4, 1, 2, 1] and longest length 7.
5. Click Reset to restart the tracing.