1. One-Liner
Map strings to integers with a polynomial hash Σ s[i]·B^i (mod M) so substring hashes update in O(1) with precomputed powers and prefix hashes.
2. The Problem It Solves
Answer substring equality / lexicographic compare queries in O(1) after O(n) preprocessing — core of Rabin–Karp, duplicate finding, and many CP tricks.
3. The Core Idea
Treat the string as a base-B number; store prefix hashes H[i]. Substring [l,r) hash = (H[r] - H[l]·P^{r-l}) mod M. Use double hashing (two moduli) to cut collision probability.
4. How It Works (Table)
| Step | What Happens |
|---|---|
| 1 | Pick B (often 911382323) and M (large prime). |
| 2 | H[i+1] = (H[i]·B + code(s[i])) mod M. |
| 3 | Precompute powB[k] = B^k mod M. |
| 4 | Substring hash via subtraction and normalize mod M. |
5. Dry Run Example
"abc": H[1]=a, H[2]=H[1]·B+b, etc. Hash of "bc" from index 1 uses H[3]-H[1]·B².
6. Key Properties
| Property | Value |
|---|---|
| Collision | Possible — verify or use two mods |
| Update | Append char O(1); substring O(1) with prefix |
7. Where It Is Used
| Domain | Use |
|---|---|
| CP | Substring palindrome, LCP by binary search |
| Plagiarism | Winnowing / k-gram fingerprints |
| Databases | Hash joins on string keys (with care) |
8. Interview Tips
Always mention modular inverse not needed if you use forward prefix with pow trick. Discuss collision and base choice.
9. Comparison with Other Algorithms
| Tool | Exact? |
|---|---|
| Suffix array | Yes, heavier |
| Hashing | Fast, probabilistic |
10. Complexity
| Metric | Value |
|---|---|
| Build | O(n) |
| Query | O(1) per substring hash |
Implementation Example (PYTHON)
class StringHash:
def __init__(self, s, base=911382323, mod=10**9 + 7):
self.mod = mod
self.pow = [1] * (len(s) + 1)
self.pref = [0] * (len(s) + 1)
for i in range(len(s)):
self.pow[i + 1] = (self.pow[i] * base) % mod
self.pref[i + 1] = (self.pref[i] * base + ord(s[i])) % mod
def substring(self, l, r):
return (self.pref[r] - self.pref[l] * self.pow[r - l]) % self.mod