PrevNext
Rare
 0/7

String Hashing

Authors: Benjamin Qi, Andrew Wang

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

Focus Problem – read through this problem before continuing!

Tutorial

Resources
CPHgood intro
cp-algocode
PAPSmany applications

Implementation - Single Base

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

C++

const ll M = 1e9 + 9, P = 9973; // Change M and P if you want to
ll pw[100001]; // Stores the powers of P modulo M
int n;
string s;
ll hsh[100001];
void calc_hashes() {
hsh[0] = 1;

Java

public static final long M = (long)1e9 + 9, P = 9973; // Change M and P if you want to
public static long pw[] = new long[100001]; // Stores the powers of P modulo M
public static int n;
public static String s;
public static long hsh[] = new long[100001];
public static void calc_hashes() {
hsh[0] = 1;

Implementation - Multiple Bases

Resources
CFregarding CF educational rounds in particular
Benq

It's generally a good idea to use two randomized bases rather than just one to decrease the probability that two random strings hash to the same value.

Solution - Searching For Strings

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

ex code for single, multiple hashes

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CEOIEasy
Show Tags

Greedy, Hashing

View Solution
CFEasy
Show Tags

DP, Hashing

Check CF
GoldNormal
Show Tags

Hashing

GoldNormal
Show Tags

Hashing, Simulation

CFHard
Show Tags

DP, Hashing

Check CF
COIHard
Show Tags

Hashing, Binsearch

External Sol

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!

Give Us Feedback on String Hashing!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext