Rare
0/7

# String Hashing

Authors: Benjamin Qi, Andrew Wang

### Prerequisites

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

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

Java

1public static final long M = (long)1e9 + 9, P = 9973; // Change M and P if you want to2
3public static long pw[] = new long[100001]; // Stores the powers of P modulo M4
5public static int n;6public static String s;7public static long hsh[] = new long[100001];8
9public static void calc_hashes() {10    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.

Feel free to file a request to complete this using the "Contact Us" button.

ex code for single, multiple hashes

## Problems

StatusSourceProblem NameDifficultyTagsSolution
CSAEasy
Show Tags

Greedy, Hashing

Check CSA
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