CONCEPT · International Master
Rolling hash
also polynomial hash · string hash
Prefix polynomial hashes make substring equality O(1). Collisions are a designed-for WA: use two moduli or 2^64 plus a prime.
Intuition
A string is a base-b number. A slice is a difference of prefixes times a power of b.
When to reach for it
- O(1) substring compare after O(n)
- Distinct k-grams
- Binary-search LCP
- Rabin–Karp matching
Usual pits
- Single 1e9+7 hash vs anti-hash tests
- Negative subtraction before the mod
- Base smaller than the alphabet without a +1 mapping
- Printing hashes instead of comparing them