Rabin–Karp Algorithm

Treat substrings of length m as numbers in base d (alphabet size, e.g. 256 for bytes). A hash function maps each length-m window T[s..s+m−1] to an integer. Instead of recomparing all m characters for every shift, update the hash in O(1) when the window slides by one: subtract the contribution of the outgoing character, add the incoming one, modulo a prime q (to keep numbers bounded).

If the hash of the window equals the hash of P, verify with an explicit character-by-character check — hashes can collide (two different strings, same hash).

1. Choose base d and modulus q (often a large prime).
2. Compute h(P) and the hash of the first window T[0..m−1].
3. For each shift s, if window hash equals h(P), compare T[s..s+m−1] to P; on match, record s.
4. Roll the hash from s to s+1 using the recurrence for polynomial rolling hash.

Monte Carlo variant: skip verification and accept hash equality (rare false positives). Las Vegas variant: always verify — our description assumes this for correctness.

Expected time can be O(n + m) when collisions are rare and verifications are few — useful for multiple patterns (compute multiple hashes) or 2D pattern search with 2D rolling hashes.

Worst case remains O(nm) if a malicious text forces many hash matches and full verifications (e.g. all windows hash-collide with P). Good hash parameters and randomization reduce collision probability in practice.

Below, h is the rolling hash of the current window; t_s denotes the numeric value of window starting at s (mod q). The roll step uses Horner-style updates.

Preprocessing / first window: O(m) to compute initial hash and pattern hash.

Rolling: O(n − m) updates, O(1) each.

Verifications: O(m) per spurious hash match. Total: O(n + m) average case with few collisions; O(nm) worst case if every window must be verified.