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

1const ll M = 1e9 + 9, P = 9973; // Change M and P if you want to
2
3ll pw[100001]; // Stores the powers of P modulo M
4
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 to
2
3public static long pw[] = new long[100001]; // Stores the powers of P modulo M
4
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

Module Progress:

Give Us Feedback on String Hashing!

Join the Discussion!

Feel free to voice your thoughts in the comments section.

PrevNext