Stage 1 · Code
String Algorithms
Rabin-Karp Hashing
Learn how rolling hashes turn repeated window comparisons into arithmetic updates, and why collision handling separates a clever idea from a correct algorithm.
Why Window-by-Window Comparison Is Slow
When you search for a pattern of length m inside a text of length n, there are n - m + 1 possible alignments. The straightforward algorithm inspects each window one character at a time until it either proves equality or finds a mismatch. That is acceptable if mismatches happen immediately, but in adversarial strings the mismatch can arrive late, meaning many windows pay almost the full m comparisons before failing.
Rabin-Karp asks a different question first: before comparing all m characters, can we cheaply summarize a whole window into one number? If the summary of the window differs from the summary of the pattern, the window cannot match and we can skip all character-by-character work. If the summaries agree, then we verify carefully to guard against collisions.
| Approach | Per-window cost | Worst-case total | What repeats |
|---|---|---|---|
| Naive substring check | Up to O(m) | O(nm) | The same characters are compared in many overlapping windows |
| Rabin-Karp with rolling hash | O(1) hash update plus occasional verification | O(nm) in the collision worst case, O(n + m) average | Only arithmetic is repeated for most windows |
| KMP | Deterministic O(1) pointer updates | O(n + m) | Pattern self-overlap is reused instead of hashes |
The algorithm shines when most windows are obviously wrong. A cheap hash comparison discards them before expensive full comparison begins.
Polynomial Hash Intuition
A common hash for strings treats characters like digits in a number system with base B. If a = 1, b = 2, and so on, then the string aba can be encoded as 1*B^2 + 2*B + 1. Different positions matter because the powers of B make the order visible. aba and baa contain the same letters, but they produce different values because their coefficients multiply different powers.
Real implementations keep the number under control with a modulus. Instead of storing the full polynomial value, they store it modulo a large prime. That keeps arithmetic fast and avoids huge integers. The trade-off is that two different strings can occasionally land on the same hash, which is why hash equality is evidence of a possible match, not a proof.
Use base B = 5 and values a=1, b=2, c=3
Hash('aba') = 1*5^2 + 2*5 + 1 = 36
Hash('bac') = 2*5^2 + 1*5 + 3 = 58
Hash('aca') = 1*5^2 + 3*5 + 1 = 41The numbers are small here on purpose so the mechanics stay visible. Production code uses a much larger base and modulus.
Without a verification step, a collision can silently produce a false match. In interview code, mention this explicitly. In production code, either double-hash or verify the substring after hash equality.
Rolling the Hash Forward
The real beauty of Rabin-Karp is that neighboring windows differ only by one outgoing character on the left and one incoming character on the right. Once you know the hash of the current window, you can compute the next hash in constant time. Remove the contribution of the outgoing character, multiply by the base to shift the remaining characters one place, then add the incoming character.
text = abacaba
pattern length = 3
base = 5
window 'aba' => 36
move to 'bac':
- remove left 'a': 36 - 1*25 = 11
- shift remaining digits: 11*5 = 55
- add new 'c': 55 + 3 = 58
move to 'aca':
- remove left 'b': 58 - 2*25 = 8
- shift: 8*5 = 40
- add new 'a': 40 + 1 = 41The update used arithmetic only. No characters inside the middle of the window were re-read.
Modulo arithmetic adds one more practical detail: subtraction can go negative. Implementations usually write something like (current - outgoing + mod) % mod before multiplying, so the value stays inside the modular range. That tiny line prevents a common bug where a mathematically correct formula produces a negative integer that no longer represents the intended hash.
Go Implementation
The implementation below uses byte-based hashing for simplicity. It computes the pattern hash, the first window hash, and the highest base power needed to remove the outgoing character. Whenever a window hash equals the pattern hash, it verifies the substring before recording a match. That final check preserves correctness even if two different strings share a hash modulo mod.
Practice Problems
Quiz
Why can Rabin-Karp update the next window hash in O(1)?
Summary
- Rabin-Karp summarizes each window with a polynomial hash instead of comparing every character immediately.
- Rolling updates make neighboring window hashes cheap because only one character leaves and one enters.
- Modulo arithmetic keeps numbers small, but collisions mean a matching hash is a candidate, not a proof.
- The technique extends naturally to repeated-substring, duplicate-detection, and substring-comparison problems.
- In interviews, always mention collision handling; it shows you understand the algorithm beyond the slogan.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.