Advanced · Module 19 · Lesson 2
Rabin–Karp
Use rolling hashes for substring matching.
15–25 min readLesson 116 of 123
Lesson 116 of 123
1d streakTheory lesson · Step-by-step
Understand Rabin–Karp
Use rolling hashes for substring matching.
Worked approach
Trace the reasoning step by step
- 1Hash the pattern and first window.
- 2Compare hashes and verify on equality.
- 3Roll to the next window.
- 4Use modular arithmetic to avoid overflow.
Concrete example
Search "bc" in "abcd" with a length-2 rolling hash.
- 1Hash "ab".
- 2Roll by removing a and adding c.
- 3Hash match for "bc" is verified.
Each next window hash is produced in O(1).
What must remain true (Loop Invariant)
The rolling hash represents the current pattern-length text window.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Search
Average O(n + m)
O(1)
Collision verification can make the worst case O(nm).When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked Rabin–Karp example without looking at the trace.
- Change one input condition and explain whether the Rabin–Karp invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.