What is the time complexity of z-algorithm?

Worst case O(n). Space complexity is O(n). Explicit comparisons either fail once or push the Z-box right, at most n times.

Z-algorithm

hard

The Z-box remembers the last useful comparison, so most positions are answered by copying from a mirror index. Because the box's right edge never decreases, the whole thing is linear.

Worst O(n)Space O(n)

Loading the z-algorithm engine…

Where to go next

KMP pattern matching

hard

The text pointer never moves backwards.

Manacher's algorithm

hard

Longest palindromic substring in O(n).

Naive pattern search

easy

Slide one place right and start over.