PrevNext
Rare
 0/7

String Hashing

Authors: Benjamin Qi, Andrew Wang

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

This section is not complete.

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

example problem, preferably smth that can't be fakesolved

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.

This section is not complete.

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

Problems

Warning!

The editorials of the Gold problems below mention hashing, but it's not difficult to pass slower solutions without hashing.

StatusSourceProblem NameDifficultyTagsSolution
CSAEasy
Show Tags

Greedy, Hashing

Check CSA
CFEasy
Show Tags

DP, Hashing

Check CF
GoldNormalExternal Sol
GoldNormalExternal Sol
CFHard
Show Tags

DP, Hashing

Check CF
COIHard
Show Tags

Hashing, Binsearch

View Solution

Module Progress:

Give Us Feedback on String Hashing!

PrevNext