# String Hashing

Authors: Benjamin Qi, Andi Qu

Contributors: Andrew Wang, Kevin Sheng

Quickly test equality of substrings with a small probability of failure.

### Prerequisites

## Tutorial

Resources | ||||
---|---|---|---|---|

CPH | ||||

cp-algo | code | |||

PAPS | many applications | |||

rng-58 |

## Implementation

As mentioned in the articles above, there is no need to calculate modular inverses.

C++

class HashedString {private:// change M and B if you wantstatic const long long M = 1e9 + 9;static const long long B = 9973;// pow[i] contains B^i % Mstatic vector<long long> pow;// p_hash[i] is the hash of the first i characters of the given string

Java

import java.util.*;public class HashedString {// Change M and B if you wantpublic static final long M = (long) 1e9 + 9;public static final long B = 9973;// pow[i] contains B^i % Mprivate static ArrayList<Long> pow = new ArrayList<>();

Python

class HashedString:# Change M and B if you wantM = int(1e9) + 9B = 9973# pow[i] contains B^i % M_pow = [1]def __init__(self, s: str):while len(self._pow) < len(s):

This implementation calculates

The hash of any particular substring $S[a : b]$ is then calculated as

using prefix sums. This is nice because the highest power of $B$ in that polynomial will always be $B^{b - a}$.

### Collision Probability

In general, when using polynomial hashing modulo a prime modulus $M$, the probability of two distinct strings having equal hashing over all possible choices of the base $B$ can be up to $\frac{n}{M}$, where $n$ is the length of the longer of the two strings. See rng-58's blog post about hashing (linked above) for how to derive this probability using the Schwarz-Zippel lemma.

Since $10^9 + 9$ is prime, the probability of collision when using this hash is
at most $\frac{N}{10^9 + 9} < 10^{-4}$, by the Schwarz-Zippel lemma. This means
that if you select any two **different** strings of length at most $N=10^5$ and a
random base modulo $10^9 + 9$ (e.g. $9973$ in the code), the probability that
they hash to the same value is at most $10^{-4}$.

### Warning!

Given a set of the hashes of $m$ distinct strings with length up to $n$, the probability of two strings having equal hashes can be up to $\frac{m^2n}{M}$ by the birthday paradox. Assuming $m$ and $n$ are on the order of $10^5$, $M=10^9+7$ is nowhere close to large enough to avoid collisions. Use a larger prime modulus such as $2^{61}-1$ (and do multiplications using 128-bit integers).

### Warning!

In contests with open hacking (in particular, CodeForces educational rounds), make sure to choose the base of your polynomial hash randomly, as mentioned here.

C++

In C++, a virtually unhackable way of generating $B$ in the implementation above is to use a random number generator seeded with a high-precision clock, as described here.

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());const ll B = uniform_int_distribution<ll>(0, M - 1)(rng);

## Example Problem - Searching For Strings

Focus Problem – try your best to solve this problem before continuing!

### Solution - One Hash

**Time Complexity:** $\mathcal O((|N| + |H|) \cdot \Sigma)$, where $\Sigma$ is
the size of the alphabet.

**Failure Probability:** $\mathcal O\left(\frac{|N||H|^2}{M}\right)$

We'll use a sliding window over $H$ to find the "matches" with $N$.

Since we don't care about relative order when comparing two substrings, we can store frequency tables of the characters in the current window and in $N$. When we slide the window, at most two values in that table change. To compare two substrings, we simply compare the 26 values in each table.

If we only needed to count the number of matches, then the above alone would
suffice (in fact, IOI 2006 Writing is just
that). However, we need to count the **distinct** permutations of $N$ in $H$, so
we need to be a bit more clever.

One way to solve this is by storing the polynomial hashes of each match in a set, since we expect different permutations to have different polynomial hashes. The answer would simply be the size of that set at the end.

Using a relatively small modulus such as $M=10^9+9$ will not pass (see the note above regarding the birthday paradox). Instead, we use $M=2^{61}-1$.

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;Code Snippet: HashedString (Click to expand)int freq_target[26], freq_curr[26];string n, h;

### Solution - Two Hashes

**Time Complexity:** $\mathcal O((|N| + |H|) \log M)$

**Failure Probability:** $\mathcal O\left(\frac{|N||H|^2}{M}\right)$

An alternative solution without frequency tables would be to hash the substrings that we're trying to match. Since order doesn't matter, we need to modify our hash function slightly.

In particular, instead of computing the **polynomial** hash of the substrings,
compute the product $(B + s_1)(B + s_2) \dots (B + s_k) \bmod M$ as the hash
(again, using two modulos). This hash is nice because the relative order of the
letters doesn't matter, as multiplication is commutative. Furthermore,
as any two strings with different frequency tables map to different polynomials
in $B$, they hash to the same value with probability at most $\frac{|N|}{M}$
over the choice of $B$.

Since this hash requires the modular inverse, there's an extra $\log M$ factor in the time complexity.

C++

#include <bits/stdc++.h>typedef long long ll;using namespace std;Code Snippet: HashedString (Click to expand)const auto M = HashedString::M;const auto B = HashedString::B;const auto mul = HashedString::mul;const auto mod_mul = HashedString::mod_mul;

## Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Very Easy | ## Show TagsHashing | |||

Silver | Easy | ## Show TagsHashing | |||

CEOI | Easy | ## Show TagsGreedy, Hashing | |||

CF | Easy | ## Show TagsDP, Hashing | |||

CF | Easy | ## Show TagsHashing | |||

Gold | Normal | ## Show TagsBinary Search, Hashing | |||

Gold | Normal | ## Show TagsHashing, Simulation | |||

RMI | Normal | ## Show TagsHashing | |||

COCI | Normal | ## Show TagsHashing, Probability | |||

COCI | Hard | ## Show TagsBinary Search, Hashing | |||

CF | Hard | ## Show TagsDP, Hashing | |||

Baltic OI | Hard | ## Show TagsHashing | |||

COCI | Very Hard | ## Show TagsDSU, Hashing | |||

COI | Very Hard | ## Show TagsBinary Search, Hashing |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!