Comparing fingerprints instead of strings
The Rabin Karp approach replaces character by character comparison with a hash comparison. It computes one number, a fingerprint, for the pattern, and a fingerprint for each window of the text the same length as the pattern. If two fingerprints differ, the strings cannot be equal and the window is skipped instantly.
The rolling trick
Recomputing a window hash from scratch every step would be slow. A rolling hash treats the window as a number in some base and updates it in constant time as the window slides:
- Subtract the contribution of the character leaving on the left.
- Multiply the remaining value by the base.
- Add the new character entering on the right.
This update is a few arithmetic operations regardless of pattern length.
Verifying real matches
Hashes can collide, meaning two different strings share a fingerprint. So when fingerprints match, the algorithm performs a direct character check to confirm a real match. With a good hash, collisions are rare, so on average almost every position is decided by a single cheap comparison and verification happens only on genuine hits.
Key idea
Rolling hash matching compares cheap numeric fingerprints, updating each window hash in constant time; equal fingerprints trigger a direct verification, so most positions are rejected with one comparison.