Manacher
Longest palindromic substring in O(n) by reusing mirrored palindrome radii.
Position 4 sits inside the palindrome centred at 3, which reaches index 6. Its mirror image about 3 is position 2, with radius 0. The mirror can be copied, but only as far as the box reaches: 2. So the starting radius is the smaller of the two, 0.
What you will see
A radius array grows; inside the current palindrome the mirror value is copied before expanding.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.
Before this
Taught by the same lesson
String Matching covers these too, in the same run.