String Hashing (Polynomial Hash) - Algorithm Tutorial | Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/string-hashing

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/algorithms/string-hashing

Repovive

String Hashing (Polynomial Hash) - Algorithm Tutorial | Repovive | Repovive

Prefix Hashes

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

Substring Hash Query

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

Collision Handling

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:

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))

Use larger modulus: Use $2^{61} - 1$ instead of $10^9 + 7$ .
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.

=

1026

H = 1 \cdot 31^2 + 2 \cdot 31^1 + 3 \cdot 31^0 = 961 + 62 + 3 = 1026

\approx 0.5\%

String Hashing (Polynomial Hash) Algorithm Tutorial

Introduction

Practice this Algorithm

Related Algorithms

Polynomial Hashing

Prefix Hashes

Substring Hash Query

Collision Handling