What is the time complexity of manacher's algorithm?

Worst case O(n). Space complexity is O(n). The right boundary only moves forward, capping total expansion at n.

Manacher's algorithm

hard

The `#` padding removes the even/odd split, and palindromes mirroring inside palindromes remove the quadratic expansion. Two ideas, one linear algorithm.

Worst O(n)Space O(n)

Loading the manacher's algorithm engine…

Where to go next

Z-algorithm

hard

How far does the prefix repeat at every position?

KMP pattern matching

hard

The text pointer never moves backwards.

Longest common subsequence

medium

Match means diagonal; mismatch means the better of two.