Rolling Hash
A fast probabilistic fingerprint for substring comparison, string sets, and prefix-based matching tricks.
Rolling Hash
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Rolling hash turns substrings into fingerprints that can be compared in constant time after preprocessing. It is not a proof-level string algorithm like KMP or suffix automaton, but it is extremely practical in contests when fast substring equality is the real need.
When to Use It
Use rolling hash when:
many substring-equality checks are needed,
deterministic linear matching is not the main bottleneck,
a tiny collision probability is acceptable or can be reduced with double hashing.
Core Idea
Interpret the string as a polynomial: \[ h(s_0 s_1 \dots s_{n-1}) = \sum s_i \cdot base^i \pmod{mod}. \] Precompute prefix hashes and powers of the base. Then any substring hash can be extracted in \(O(1)\).
Key Insight
The ``rolling'' part is that neighboring substrings differ by one removed character and one added character. Prefix preprocessing packages that relation so individual substring queries become constant-time arithmetic.
Operations / Main Technique
precompute powers and prefix hashes,
query a substring hash in \(O(1)\),
compare two substrings by comparing their normalized hashes.
Worked example.
If I need to compare \(s[l_1 \dots r_1]\) and \(s[l_2 \dots r_2]\) many times, rolling hash turns each comparison into two prefix-difference computations instead of a character-by-character scan.
Correctness Intuition
The hash is designed so concatenation and prefix removal behave algebraically. Taking a prefix difference isolates the contribution of one substring, and multiplying by the right power aligns hashes from different positions.
The algorithm is probabilistic: equal hashes strongly suggest equal substrings, but collisions are possible.
Complexity Analysis
preprocessing: \(O(n)\),
substring hash query: \(O(1)\),
memory: \(O(n)\).
Implementation
The reference code uses one modulus and one base for clarity. In harder problems I often upgrade that to double hashing or 64-bit hashing to reduce collision risk.
Common Pitfalls
Forgetting that hashing is probabilistic.
Using a poor base or modulus choice.
Comparing unnormalized substring hashes from different positions.
Treating hash equality as a formal proof in adversarial settings.
Variants / Extensions
Double hashing with two moduli.
64-bit hashing with natural overflow.
Binary search plus hashing for longest common prefix queries.
Practice Problems
Many substring-equality queries on one string.
Detect repeated substrings quickly.
Binary-search the longest duplicate or longest common substring length.
References
Code
Contest-ready reference implementation for the idea explained above.
struct RollingHash {
static constexpr long long MOD = 1'000'000'007;
static constexpr long long BASE = 911382323;
vector<long long> power;
vector<long long> pref;
explicit RollingHash(const string& s) : power(s.size() + 1, 1), pref(s.size() + 1, 0) {
for (int i = 0; i < (int)s.size(); ++i) {
power[i + 1] = (__int128)power[i] * BASE % MOD;
pref[i + 1] = (( __int128)pref[i] * BASE + s[i]) % MOD;
}
}
long long get_hash(int l, int r) const {
long long value = (pref[r + 1] - (__int128)pref[l] * power[r - l + 1]) % MOD;
if (value < 0) value += MOD;
return value;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.