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?
- When the rolling hash of a window equals the hash of the pattern, why do we still compare the characters?
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.
Find every position where a pattern of length M occurs in a text of length N, in average `O(N + M)`.
Hash the pattern and the first window with a polynomial hash modulo a large prime. Slide the window by removing the outgoing character, multiplying by the base, and adding the incoming one. On a hash match, compare the characters to rule out a collision.
Approach: The `O(1)` window update is what removes the factor of M from each comparison.
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