Fingerprinting equal-length windows
The algorithm hashes a length-m pattern and an equally long text window. Moving right removes the outgoing character’s contribution and adds the incoming one, avoiding a complete rehash of all m positions.
A polynomial representation treats characters as radix digits modulo a chosen number, with a precomputed power for removal. Modulus, overflow and character encoding are implementation details needed to realize the formula correctly.
References: [1]
Deciding whether to verify collisions
Different fingerprints reject a window, but equal fingerprints can collide. Princeton verifies candidate characters, so equal hashes alone cannot produce a false exact hit; random choices mainly affect verification work.
A Monte Carlo version omits verification and can report false positives. Additional fingerprints or larger moduli change collision risk without making a finite fingerprint injective over all strings. The error policy is part of the algorithm contract.
References: [1]
Separating rolling and verification costs
With fixed-size modular arithmetic, rolling work is O(n+m), but exact candidate checks can each inspect m characters. Collisions or many candidates add work, leaving O(nm) worst cases for a verifying version.
Several equal-length patterns can be grouped by fingerprints and checked during one text scan, with exact resolution inside candidate buckets. This rolling fingerprint is a search filter rather than a cryptographic commitment against deliberate forgery.