Pattern Reference
String Hashing
"Rolling hash, Rabin-Karp, double hash, detect plagiarism, longest common substring via binary search + hash."
Loading...
Deep Dive Tutorial
String hashing converts a substring to a number in O(1) time using prefix hash arrays. The polynomial hash: hash(s) = s[0]*p^(n-1) + s[1]*p^(n-2) + ... + s[n-1]*p^0 (mod M). Precompute prefix hashes and powers. Then hash(s[l..r]) = (prefix[r+1] - prefix[l] * pow[r-l+1]) mod M. Two equal hashes = probably equal strings (with double hash, near-certainly).
Rolling hash template — double hashing for safety
class RollingHash {
constructor(s) {
const n = s.length;
const [P1, P2] = [31, 37];
const [M1, M2] = [1e9 + 7, 1e9 + 9];
this.h1 = new Array(n + 1).fill(0);
this.h2 = new Array(n + 1).fill(0);
this.p1 = new Array(n + 1).fill(1);
this.p2 = new Array(n + 1).fill(1);
for (let i = 0; i < n; i++) {
const c = s.charCodeAt(i) - 96; // a=1, b=2, ...
this.h1[i+1] = (this.h1[i] * P1 + c) % M1;
this.h2[i+1] = (this.h2[i] * P2 + c) % M2;
this.p1[i+1] = this.p1[i] * P1 % M1;
this.p2[i+1] = this.p2[i] * P2 % M2;
}
this.M1 = M1; this.M2 = M2;
}
// Get hash of s[l..r] (0-indexed, inclusive)
get(l, r) {
const len = r - l + 1;
const v1 = (this.h1[r+1] - this.h1[l] * this.p1[len] % this.M1 + this.M1 * 2) % this.M1;
const v2 = (this.h2[r+1] - this.h2[l] * this.p2[len] % this.M2 + this.M2 * 2) % this.M2;
return v1 * 1e9 + v2; // combine both hashes
}
equal(l1, r1, l2, r2) { return this.get(l1, r1) === this.get(l2, r2); }
}
// Usage:
// const rh = new RollingHash("abcabc");
// rh.equal(0, 2, 3, 5) → true (both "abc")Worked Problems
hash
Rolling hash key formulas:
- Prefix hash: h[i+1] = (h[i] * P + c) % M
- Substring hash: (h[r+1] - h[l] * pow[len]) % M
- Always add M before % to avoid negative (JS modulo quirk)
Collision safety:
- Single hash: ~1/M collision chance per comparison (M ≈ 10^9)
- Double hash: ~1/M² ≈ 10^{-18} per comparison — effectively zero
When to use: Comparing many substrings (O(1) each), binary search on string length (check in O(n)), Rabin-Karp rolling window search.
vs KMP/Z-function: Use KMP/Z for single pattern search. Use hash when you need to compare arbitrary substring pairs.
- Prefix hash: h[i+1] = (h[i] * P + c) % M
- Substring hash: (h[r+1] - h[l] * pow[len]) % M
- Always add M before % to avoid negative (JS modulo quirk)
Collision safety:
- Single hash: ~1/M collision chance per comparison (M ≈ 10^9)
- Double hash: ~1/M² ≈ 10^{-18} per comparison — effectively zero
When to use: Comparing many substrings (O(1) each), binary search on string length (check in O(n)), Rabin-Karp rolling window search.
vs KMP/Z-function: Use KMP/Z for single pattern search. Use hash when you need to compare arbitrary substring pairs.