What is the time complexity of kmp pattern matching?

Worst case O(n + m). Space complexity is O(m). The text index only ever advances, capping the scan at n steps.

KMP pattern matching

hard

The failure function records, for each prefix, the longest proper prefix that is also a suffix - so a mismatch slides the pattern forward without re-reading a single character.

Worst O(n + m)Space O(m)

Loading the kmp pattern matching engine…

Where to go next

Naive pattern search

easy

Slide one place right and start over.

Z-algorithm

hard

How far does the prefix repeat at every position?

Rabin-Karp

medium

A rolling hash, and why verification is not optional.