Rolling hash (Rabin-Karp)
Overview
A string-searching algorithm that uses a rolling hash function to find pattern matches in O(N) average time.
It avoids rescanning the entire substring on every shift, allowing multi-pattern search and plagiarism detection.
Where used: Plagiarism detection (comparing many document chunks), Rsync protocol (finding matching file blocks)
Why it exists
Problem: We want to find a substring of length M inside a string of length N. A naive search takes O(N * M). Hash mapping the substrings takes O(M) time per hash, still giving O(N * M).
Naive approach: Slide a window of size M and use `string == target` which takes O(M) time per comparison.
Better idea: Treat the string window as a base-26 (or base-256) number. When sliding the window by 1 character, we can update the hash mathematically in O(1) time by subtracting the outgoing character's value and adding the incoming character's value.
Why learn this
- It is the basis for advanced string matching algorithms.
- It teaches polynomial hashing, which is a powerful technique for String DP problems.
Mental model
Like a rolling odometer. If you have the number 1234 and you slide a 3-digit window right to get 2345, you don't read '2, 3, 4, 5' from scratch. You take 1234, subtract 1000, multiply by 10, and add 5.
Rabin-Karp converts strings to integer hashes using a polynomial hash function modulo a large prime. When the window slides, the old hash is updated in O(1) time. If the hash of the window matches the hash of the target, we do a full string comparison to confirm it's not a collision.
Repeated decision: Slide the window: Subtract the contribution of the outgoing character, multiply by the base, add the incoming character, and modulo the prime.
Deep dive
The core of Rabin-Karp is the **Polynomial Rolling Hash**. We choose a base `B` (like 256 for ASCII) and a large prime modulus `M` (to prevent integer overflow).
A string like "abc" is hashed as: `(ascii('a') * B^2 + ascii('b') * B^1 + ascii('c') * B^0) % M`.
Now, suppose our window slides from "abc" to "bcd". We need to update the hash. Instead of recalculating from scratch, we observe the math:
1. Subtract the leading character: Remove `ascii('a') * B^2`.
2. Shift everything left: Multiply the entire result by `B`.
3. Add the new character: Add `ascii('d') * B^0`.
4. Apply modulo `M` at every step to prevent overflow.
This sequence of arithmetic operations takes `O(1)` time. Thus, we can slide a window of size `M` across a text of size `N` in `O(N)` time. If the hash of our window matches the target hash, we do an `O(M)` character-by-character check to ensure it's not a hash collision. Assuming very few collisions, the average time complexity is `O(N + M)`.
Key points
- Complexity: Average Time is O(N + M). Worst-case Time (if every hash collides) is O(N * M). Space is O(1).
- Multi-pattern search: Rabin-Karp shines when searching for MULTIPLE patterns of the same length simultaneously. You just check if the rolling hash exists in a Hash Set of target hashes.
Pattern: Rolling Hash
Recognition cues:
- Find longest repeated substring
- String matching in O(N) time
Failure signals
- The problem asks for substring searches but the lengths of the targets vary wildly (Rabin-Karp needs a fixed window size).
Engineering examples
Rsync utility
Updating files across a network by only sending the parts that changed.
Rsync uses a rolling checksum (similar to a rolling hash) to find blocks of data in the new file that already exist in the old file.
When not to use
- Single pattern search in a single text: KMP (Knuth-Morris-Pratt) guarantees O(N+M) worst-case time without worrying about prime numbers, modulo arithmetic, or hash collisions.
Common mistakes
- Forgetting the modulo math rules: When subtracting the leading character, the result might become negative before the modulo. In languages like C++ or Java, `(-5) % M` is negative. You must do `(val % M + M) % M` to keep it positive.
- Not double-checking collisions: Hashes are not unique. Two completely different strings can hash to the same integer. If hashes match, you MUST explicitly compare the strings character by character.
Recall questions
- Why is Rabin-Karp's worst-case time complexity O(N * M)?
- What three mathematical operations are performed when sliding a rolling hash window?
Understanding checks
If your base is 10, how do you mathematically shift the number 456 to 567 using O(1) rolling hash logic?
Subtract 400 (4 * 10^2) to get 56. Multiply by 10 to get 560. Add 7 to get 567.
This is exactly the math used in Rabin-Karp polynomial hashing, just with base 256 or a prime base instead of base 10.
A developer writes `hash = (hash - char_val * pow_base) % MOD` and gets incorrect answers. What is wrong?
In many languages, modulo of a negative number is negative. The subtraction can make the value negative, so it must be adjusted: `(hash - val) % MOD + MOD) % MOD`.
Hash arrays or comparisons expect positive integers. A negative hash will fail to match.
Questions & answers
Repeated DNA Sequences
Find all 10-letter-long sequences that occur more than once. Use a rolling hash to track seen hashes in O(N).
Approach: Since the alphabet is just 'ACGT', the base can be 4, entirely avoiding collisions if you pack them in an integer.
Practice tasks
Repeated DNA Sequences
Given a string `s` that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Continue learning
Previous: Hash Tables
Previous: GCD, LCM & modular arithmetic