Course contentsShow
← Computer Science
Lesson 832 of 2,87219. Searching and SelectionFree lesson

Rabin-Karp Algorithm: Rolling Hash

Learn the Rabin-Karp algorithm using rolling hash functions to achieve average O(n+m) time for pattern matching.

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:

  1. Removing the contribution of the leftmost character leaving the window
  2. 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.