What is the time complexity of naive pattern search?

Best case O(n). Average case O(n). Worst case O(n·m). Space complexity is O(1).

Naive pattern search

easy

After matching four characters and failing on the fifth, it throws away everything it learned. Every faster matcher is a different answer to 'how do we keep that?'

Best O(n)Average O(n)Worst O(n·m)Space O(1)

Loading the naive pattern search engine…

Where to go next

KMP pattern matching

hard

The text pointer never moves backwards.

Rabin-Karp

medium

A rolling hash, and why verification is not optional.

Z-algorithm

hard

How far does the prefix repeat at every position?