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

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

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

Java

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

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

ex code for single, multiple hashes

## Problems

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

CSA | Easy | ## Show TagsGreedy, Hashing | Check CSA | ||

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:

## Give Us Feedback on String Hashing!

### Join the Discussion!

Feel free to voice your thoughts in the comments section.