Rabin-Karp Algorithm: Rolling Hash
You'll learn how the Rabin-Karp algorithm uses a clever rolling hash technique to search for patterns in text efficiently, achieving average O(n+m) time complexity.
The Core Idea
The naive string search approach checks every position in the text against the pattern, leading to O(n×m) comparisons in the worst case. The Rabin-Karp algorithm improves this by using a hash function to quickly filter out positions that can't possibly match.
Here's the key insight: instead of comparing characters one-by-one, compute a hash value for the pattern and compare it against hash values of text substrings. Only when hashes match do you verify with a character-by-character comparison.
The Rolling Hash Magic
The "rolling" part is what makes this algorithm elegant. Think of it like a sliding window across your text. After computing the hash for one substring, you don't recalculate from scratch for the next position. Instead, you "roll" the hash by:
- Removing the contribution of the leftmost character leaving the window
- Adding the contribution of the new rightmost character entering the window
This update happens in constant time O(1), making the overall algorithm O(n+m) on average—O(m) to hash the pattern, O(n) to roll through the text.
Why It Works
The hash acts like a fingerprint. Different strings usually produce different hashes (though collisions can occur). By comparing fingerprints first, you eliminate most non-matching positions instantly. When a hash collision happens, the extra character comparison catches it, ensuring correctness.
Key Takeaway: The Rabin-Karp algorithm's rolling hash transforms string matching from repeatedly comparing full substrings into computing incremental hash updates in constant time, achieving O(n+m) average performance.