CodeWithYash

Foundation · Module 5 · Lesson 5

Rolling hash

Incrementally hash windows and substrings.

15–25 min readLesson 31 of 123

Lesson 31 of 123

1d streak

Rolling Hash & The Rabin-Karp Algorithm

Computing a hash from scratch for every window of length $m$ takes $O(m)$ time, giving an $O(n cdot m)$ overall search. A Rolling Hash updates the hash of an active window in O(1) time when the window slides by one position: subtracting the outgoing character and adding the incoming character.

Polynomial Rolling Hash Window Transition (Base B, Modulo M)
Window 1: "cat" -> Hash = ( 'c'*B^2 + 'a'*B^1 + 't'*B^0 ) % M

Slide window to "ate":
1. Subtract outgoing character 'c' * B^2:
   Hash = ( Hash - 'c' * B^2 ) % M

2. Multiply by base B (shifts all powers by 1):
   Hash = ( Hash * B ) % M

3. Add incoming character 'e':
   Hash = ( Hash + 'e' ) % M

Result: In strictly O(1) time, we have the valid hash of "ate"!

Use it when

Use Rolling Hash (Rabin-Karp) for multiple pattern search, repeated substring detection of fixed length, or longest duplicate substring binary search.

Reconsider when

Use KMP or Z-algorithm when single pattern matching without hash collisions is required.

Cost Model

Complexity & Trade-offs

Rabin–Karp scan
Average O(n + m)
O(1)
Worst case rises with many collisions.

When to use it

  • Presence, uniqueness, frequency, complement, and previously seen state queries.
  • Replacing repeated scans with indexed history.
  • Grouping values by a canonical key.

Common mistakes

  • Assuming hash lookup has a deterministic O(1) worst case.
  • Updating the map before a query that requires a distinct earlier item.
  • Using mutable or inconsistent keys.

Practice prompts

  • Reproduce the worked Rolling hash example without looking at the trace.
  • Change one input condition and explain whether the Rolling hash 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.