Advanced · Module 19 · Lesson 2 of 4
Rolling hash and Rabin-Karp
A rolling hash updates the hash of a sliding window in constant time as one character leaves and another enters. Rabin-Karp uses it to compare a pattern against every window of a text, checking characters only when the hashes match.
By the end you can
- Compute a polynomial hash of a string and roll it across a window in O(1) per step
- Find pattern occurrences with Rabin-Karp, verifying hash matches to rule out collisions
- Choose the base and modulus, and combine rolling hashes with binary search for substring problems
Builds on Tries, What a hash function does.
01 · A question first
Comparing a 1,000-character pattern against every position of a 1,000,000 character text, character by character, can take a billion comparisons. Comparing two numbers takes one. If each window of the text could be turned into a number in constant time, matching would be nearly free. How can a window's hash be updated without rereading the window?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Matching by numbers
- A hash that rolls
- Collisions and the choice of modulus
- Beyond a single pattern
- Where rolling hashes are used
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem