String Hashing (Polynomial Hash) Algorithm Tutorial

String Hashing is a technique to compare substrings in $O(1)$ time after $O(n)$ preprocessing.

The Problem: Comparing two substrings of length $k$ takes $O(k)$ time. With $q$ queries, the naive approach is $O(q \cdot k)$.

The Idea: Map each string to a number (its "hash"). If two strings have different hashes, they are definitely different. If they have the same hash, they are probably equal.

Applications:

• Substring equality checks
• Pattern matching (Rabin-Karp algorithm)
• Finding repeated substrings
• Longest common substring problems

A polynomial hash treats a string as a polynomial evaluated at some base $b$, modulo a prime $p$.

For string $s = s_0 s_1 \ldots s_{n-1}$: $H(s) = (s_0 \cdot b^{n-1} + s_1 \cdot b^{n-2} + \ldots + s_{n-1} \cdot b^0) \mod p$

Typical choices:

• Base $b = 31$ or $b = 37$ (prime, larger than alphabet size)
• Modulus $p = 10^9 + 7$ (large prime)
• Character value: $a = 1, b = 2, \ldots, z = 26$

Example: Hash of "abc" with $b = 31$, $p = 10^9 + 7$: $H = 1 \cdot 31^2 + 2 \cdot 31^1 + 3 \cdot 31^0 = 961 + 62 + 3 = 1026$

To query substring hashes in $O(1)$, precompute prefix hashes.

Define $prefix[i]$ as the hash of $s[0..i-1]$: $prefix[i] = (s_0 \cdot b^{i-1} + s_1 \cdot b^{i-2} + \ldots + s_{i-1}) \mod p$

Building prefix hashes:

prefix[0] = 0
for i from 0 to n-1:
    prefix[i+1] = (prefix[i] * b + s[i]) mod p

Also precompute powers of $b$:

power[0] = 1
for i from 1 to n:
    power[i] = (power[i-1] * b) mod p

Time: $O(n)$ preprocessing

To get the hash of substring $s[l..r]$ (0-indexed):

$H(s[l..r]) = \frac{prefix[r+1] - prefix[l] \cdot b^{r-l+1}}{1} \mod p$

In practice (since we cannot divide): $H(s[l..r]) = (prefix[r+1] - prefix[l] \cdot power[r-l+1]) \mod p$

Make sure to handle negative modulo:

function hash(l, r):
    len = r - l + 1
    h = prefix[r+1] - prefix[l] * power[len]
    return ((h mod p) + p) mod p

Comparing substrings:

function equal(l1, r1, l2, r2):
    if (r1 - l1) != (r2 - l2):
        return false
    return hash(l1, r1) == hash(l2, r2)

Time: $O(1)$ per query

Hash collisions occur when two different strings have the same hash.

Probability: With modulus $p$ and $n$ queries, collision probability is roughly $\frac{n^2}{2p}$.

For $p = 10^9 + 7$ and $n = 10^5$: probability $\approx 0.5\%$.

Strategies to reduce collisions:

1. Double hashing: Use two different (base, modulus) pairs. Probability drops to $\approx 0.000005\%$.

equal = (hash1(l1,r1) == hash1(l2,r2)) AND
        (hash2(l1,r1) == hash2(l2,r2))

1. Use larger modulus: Use $2^{61} - 1$ instead of $10^9 + 7$.

2. Randomize base: Choose base randomly at runtime.

For competitive programming, single hashing with $p = 10^9 + 7$ is usually sufficient, but be aware of anti-hash test cases.