String matching: KMP, Z-function and rolling hashes · 2 of 2 Advanced
Rolling hashes
Turn substrings into numbers that update in constant time as a window slides, and compare any two substrings with prefix hashes.
- String Hashing Polynomial hashes, substring hashes from prefix hashes, counting distinct substrings, and how the chance of a collision depends on the modulus. cp-algorithms.com (opens in a new tab)
- Hashing A string-hashing template with its collision analysis, searching with one and with two hashes, and practice problems. usaco.guide (opens in a new tab)
- Open Data Structures, Chapter 5: Hash tables Section 5.3 hashes arrays and strings with a polynomial evaluated at a random point modulo a prime, and bounds the chance that two different sequences collide by counting the polynomial's roots. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code. opendatastructures.org (opens in a new tab)