Rolling Hash

A hash that can be updated in $O(1)$ when the window slides by one character — the basis of Rabin-Karp and of most sliding-window string techniques.

The update

For the polynomial hash $H={\sum }_i{s}_i{B}^{k-1-i}$ over a window of length $k$:

$H_{\text{new}}=(H_{\text{old}}-s_{\text{out}}\cdot B^{k-1})\cdot B+s_{\text{in}}(\mathrm{mod}M).$

long long h = 0, pw = 1;
for (int i = 0; i < k; i++) { h = (h * B + s[i]) % M; if (i) pw = pw * B % M; }
// slide from window [i, i+k) to [i+1, i+k+1)
h = ((h - s[i] * pw % M + M * M) % M * B + s[i + k]) % M;

Watch the sign: subtracting before taking the modulus can go negative, so add a multiple of $M$ first.

Rolling hash vs prefix hashing

	Rolling hash	Prefix hashing
Memory	$O(1)$	$O(n)$
Arbitrary substring	✘ (only the current window)	✔ $O(1)$
Sliding window	✔ $O(1)$	✔ $O(1)$
Streaming input	✔	✘
Code	shorter	slightly longer

Prefix hashing is strictly more capable and almost always what you want in a contest. Rolling hash matters for streaming (the text does not fit in memory) and for algorithms where the $O(1)$ memory is the point.

Where rolling hashes are the right tool

Rabin-Karp matching

Hash the pattern once, roll a window across the text, verify on a hash match. $O(n+m)$ expected. See Rabin-Karp.

2D pattern matching

Hash each row of the pattern, then roll horizontally across each text row to get a per-position row hash. Now treat each text column of row-hashes as a 1D string and roll vertically. $O(nm)$ for an $n\times m$ text — the standard solution to “find this rectangular pattern in this grid”.

Rabin fingerprinting / content-defined chunking

Split a data stream at positions where the rolling hash has $k$ trailing zero bits. Because the boundaries depend on content rather than offset, inserting bytes at the start does not shift every subsequent chunk — which is why rsync, borg and most deduplicating backup systems use exactly this.

Cyclic polynomial (Buzhash)

An alternative rolling hash using rotations and XOR instead of multiplication:

$H=\mathrm{rot}(H,1)\oplus \mathrm{rot}(h(s_{\text{out}}),k)\oplus h(s_{\text{in}}).$

Faster (no multiplication) and with better bit distribution, at the cost of weaker theoretical guarantees.

Collision defence

The same rules as prefix hashing:

1. Randomise the base at runtime.
2. Use $M=2^{61}-1$, not $10^9+7$ and never $2^{64}$ overflow.
3. Verify on match when the number of candidate positions is small — this makes Rabin-Karp deterministic in its output, with only the running time being probabilistic.
4. Double hashing if the number of comparisons is large.

Anti-hash tests

A fixed base modulo $2^{64}$ is broken by the Thue-Morse sequence in $O(\log )$ length, and any fixed $(B,M)$ is vulnerable to a precomputed birthday attack. On Codeforces, assume every hashing problem has an anti-hash test. Randomising the base at runtime costs one line and defeats all of them.

Choosing a base

Any value in $[\sigma ,M-2]$ works, chosen at random. It should exceed the alphabet size so that distinct characters cannot alias, and be coprime to $M$ (automatic when $M$ is prime).

See also: String Hashing · Rabin-Karp · Polynomial Hashing