Rabin-Karp hashes a window of the text and compares to the pattern's hash. When they match, it verifies character-by-character (guarding against spurious hash collisions). The trick is the rolling hash: sliding the window one step costs O(1), so the total run is O(n + m) average — even faster in practice when the alphabet is large or the pattern is long, and it generalises cleanly to multi-pattern search.
H(s) = (s[0]·bm-1 + s[1]·bm-2 + … + s[m-1]) mod q.
To slide right by one: H' = ((H − sold·bm-1)·b + snew) mod q.
Michael O. Rabin and Richard M. Karp published this in 1987. The naive approach is O(n·m) because comparing each window costs O(m). Their insight: hash the window into a fixed-size fingerprint, and choose a hash you can update in O(1) as the window slides. When fingerprints match, verify the full string to rule out a spurious collision. The polynomial hash mod a prime q keeps values bounded and gives an expected collision probability of ~1/q. Rabin-Karp really earns its keep in multi-pattern search — hash k patterns, keep the fingerprints in a hash set, then scan the text once. Bioinformatics k-mer indexing (BLAST, minhash), plagiarism detection, and Bloom-filter-backed content dedup all live on this idea.