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

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;

Java

public static final long M = (long)1e9 + 9, P = 9973; // Change M and P if you want topublic static long pw[] = new long[100001]; // Stores the powers of P modulo Mpublic 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 | |||
---|---|---|---|

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.

## Solution - Searching For Strings

### This section is not complete.

ex code for single, multiple hashes

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CEOI | Easy | ## Show TagsGreedy, Hashing | View Solution | |||

CF | Easy | ## Show TagsDP, Hashing | Check CF | |||

Gold | Normal | ## Show TagsHashing | ||||

Gold | Normal | ## Show TagsHashing, Simulation | ||||

CF | Hard | ## Show TagsDP, Hashing | Check CF | |||

COI | Hard | ## Show TagsHashing, 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.