Karp-Rabin

First filter algorithm using an hashing function. It works in $O(mn)$-time complexity but has an $O(n + m)$ expected running time.

Appeared in:

• [73]: Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31(2), 249–260 (1987), http://dx.doi.org/10.1147/rd.312.0249 ↗