String Hashing — Polynomial Rolling Hash

Prefix hashes

long[] h = new long[n + 1];
long[] pw = new long[n + 1];
pw[0] = 1;
for (int i = 0; i < n; i++) {
  h[i+1] = (h[i] * BASE + s.charAt(i)) % MOD;
  pw[i+1] = pw[i] * BASE % MOD;
}
long substringHash(int l, int r) {
  return (h[r+1] - h[l] * pw[r-l+1] % MOD + MOD*MOD) % MOD;
}

Double hashing

Two independent (BASE, MOD) pairs. Collision probability ~1/p². Choose primes ~10^18 (or 10^9 with 128-bit multiply).

Applications

Set of substrings. Compare substrings equal in O(1). Distinct substring count. LCS in O(N+M) with hashing.

Adversarial input

Random BASE/MOD per run defeats attackers. Fixed hashes vulnerable to hash flooding.