Matching by hashing
Rabin Karp searches for a pattern in text by comparing hash values instead of characters. Hash the pattern once, then hash each text window of the same length and compare numbers. Comparing two numbers is fast, so most positions are rejected instantly.
The rolling hash
Recomputing a window's hash from scratch at every position would be slow. The trick is a rolling hash that updates in constant time as the window slides.
- Treat the window as a number in some base.
- When the window moves right, remove the leaving character's contribution and add the entering character.
- This update is a few arithmetic operations, independent of window length.
Handling collisions
Two different strings can share a hash, a collision. So a hash match is only a candidate. Rabin Karp confirms each candidate with a direct character comparison. With a good hash and a large modulus, collisions are rare, so the expected running time is proportional to the text length plus matches.
A weak hash can degrade the worst case, so the modulus and base choice matter, especially when an adversary controls the input.
Key idea
Rabin Karp slides a rolling hash across the text and verifies only the windows whose hash matches the pattern, making most positions cheap to reject.