Rare
0/7
String Hashing
Author: Benjamin Qi
Prerequisites
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 | |||
|---|---|---|---|
| CPH | good intro | ||
| cp-algo | code | ||
| PAPS | many 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 toll pw[100001]; // Stores the powers of P modulo Mint n;string s;ll hsh[100001];void calc_hashes() {hsh[0] = 1;
Implementation - Multiple Bases
| Resources | |||
|---|---|---|---|
| CF | regarding 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.
| Status | Source | Problem Name | Difficulty | Tags | Solution |
|---|---|---|---|---|---|
| CSA | Easy | Show TagsGreedy, Hashing | Check CSA | ||
| CF | Easy | Show TagsDP, Hashing | Check CF | ||
| Gold | Normal | External Sol | |||
| Gold | Normal | External Sol | |||
| CF | Hard | Show TagsDP, Hashing | Check CF | ||
| COI | Hard | Show TagsHashing, Binsearch | View Solution |