Rolling Hash & Rabin-Karp

Polynomial and prefix hashes, choosing the base and modulus, collision odds, anti-hash tests, and double hashing.

0 / 5 solved

Question Tags Difficulty Success

1. Hashing The Word Bad

string-hashingpolynomial-hash +1

Medium —

2. The Modulo Went Negative

string-hashingmodular-arithmetic +1

Medium —

3. When A Means Zero

string-hashingcollisions +1

Medium —

4. Ninety Nine Percent Doomed

string-hashingcollision-probability +2

Hard —

5. The Overflow Modulus Trap

string-hashinganti-hash-tests +1

Hard —

Learning Resources

cp-algorithms, String hashing

cp-algorithms, Rabin-Karp algorithm

Algorithms, 4th Edition, Substring Search (Rabin-Karp)

Up next

5 of 5 questions here are still unsolved.

Next module Tries & Prefix Structures