AlgoScope

Manacher

Longest palindromic substring in O(n) by reusing mirrored palindrome radii.

String algorithms, algorithm, advanced
Position 4 mirrors 2. Starting radius 0.012345678910111213141516tr#a#b#a#c#a#b#a#d#0103

String Matching: Longest palindrome, odd and even at once

Decision, step 8 of 32

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.

How string matching works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

Taught by the same lesson

String Matching covers these too, in the same run.