Manacher
Longest palindromic substring in O(n) by reusing mirrored palindrome radii.
String Matching: Longest palindrome, odd and even at once
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.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
Taught by the same lesson
String Matching covers these too, in the same run.