Rabin-Karp — Hash-Based Pattern Matching

Rolling hash

long h = 0;
long pow = 1;
for (int i = 0; i < m; i++) { h = (h * BASE + p.charAt(i)) % MOD; if (i > 0) pow = pow * BASE % MOD; }
// slide: newH = ((oldH - t.charAt(i-m) * pow) * BASE + t.charAt(i)) % MOD

Collisions

Hash match → verify with actual comparison. Double hashing (two moduli) reduces collision probability to ~1/p².

Multi-pattern

Multi-pattern Rabin-Karp: hash multiple patterns, check window against set of hashes. Base of Aho-Corasick alternatives.

Applications

Plagiarism (multiple documents). MOSS. Real-time text streaming search.