What is the Rabin-Karp Algorithm?
Learn how Rabin-Karp uses a rolling hash for fast substring search, its complexity, and multi-pattern use cases.
Expected Interview Answer
Rabin-Karp finds pattern occurrences in a text by hashing the pattern and every equal-length substring of the text using a rolling hash, comparing hash values first and only doing a full character check when hashes match, achieving average-case O(n + m) time and making it especially strong for searching many patterns at once.
The rolling hash is the key trick: instead of recomputing a hash from scratch for every window of the text, the hash of the next window is derived from the previous one in O(1) by removing the leading character's contribution and adding the trailing character's, typically under a large prime modulus to limit collisions. When a window's hash equals the pattern's hash, the algorithm still verifies with a direct character comparison, because different substrings can collide to the same hash (a false positive) even though a real match never produces a different hash (no false negatives). Worst-case time degrades to O(n*m) if many collisions force repeated verification, but with a well-chosen modulus this is rare in practice. Rabin-Karp shines when searching for multiple patterns simultaneously, such as plagiarism detection across many documents, since all pattern hashes can be checked against one rolling scan of the text.
- Average O(n + m) time via O(1) rolling hash updates
- Extends naturally to searching multiple patterns in one pass
- Simple to implement compared to automaton-based matchers
- Well suited to plagiarism and duplicate-detection systems
AI Mentor Explanation
Rabin-Karp is like a scorer using a quick checksum to spot a repeated over pattern across a full match commentary without re-reading every ball in detail each time. Instead of comparing all six deliveries of every window ball by ball, the scorer keeps a rolling checksum of the current six-ball window, updating it in one step by dropping the oldest ball and adding the newest. Only when a window checksum matches the target over does the scorer actually compare deliveries ball by ball, since two different overs could coincidentally produce the same checksum. This rolling-update trick is what lets the scorer scan the entire commentary in roughly one pass instead of re-summing six balls at every position.
Step-by-Step Explanation
Step 1
Hash the pattern and first window
Compute the pattern's hash and the hash of the text's first equal-length window using the same base and modulus.
Step 2
Slide the window with a rolling update
Remove the leading character's contribution and add the trailing character's in O(1) to get the next window's hash.
Step 3
Compare hashes before characters
If the window hash equals the pattern hash, verify with a direct character comparison to rule out a collision.
Step 4
Repeat across the text
Continue sliding and comparing until the window reaches the end of the text, recording every verified match.
What Interviewer Expects
- Explain the rolling hash update and why it is O(1) per window
- Clarify why a hash match still requires character verification (avoiding false positives)
- State average O(n + m) time and worst-case O(n*m) with many collisions
- Mention the multi-pattern search advantage over KMP
Common Mistakes
- Skipping character verification after a hash match, causing false positives
- Recomputing the hash from scratch for every window instead of rolling it
- Using a modulus too small, causing frequent collisions and worst-case behavior
- Confusing Rabin-Karp with KMP as if they use the same failure-function mechanism
Best Answer (HR Friendly)
“Rabin-Karp finds a pattern in text by hashing chunks instead of comparing letter by letter every time, using a rolling formula to update the hash cheaply as the window slides. I'd pick it when I need to search for many patterns at once, like checking a document against a big list of banned phrases.”
Code Example
def rabin_karp(text, pattern, base=256, mod=1_000_000_007):
n, m = len(text), len(pattern)
if m == 0 or m > n:
return []
high_order = pow(base, m - 1, mod)
pattern_hash = 0
window_hash = 0
for i in range(m):
pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
window_hash = (window_hash * base + ord(text[i])) % mod
matches = []
for i in range(n - m + 1):
if window_hash == pattern_hash and text[i:i + m] == pattern:
matches.append(i)
if i < n - m:
window_hash = (window_hash - ord(text[i]) * high_order) % mod
window_hash = (window_hash * base + ord(text[i + m])) % mod
window_hash %= mod
return matchesFollow-up Questions
- How would you extend Rabin-Karp to search for multiple patterns in one pass?
- Why does Rabin-Karp still need a character comparison after a hash match?
- How would you choose the modulus and base to minimize collisions?
- How does Rabin-Karp compare to KMP for a single long pattern?
MCQ Practice
1. What makes Rabin-Karp's window hash update efficient?
The rolling hash removes the outgoing character and adds the incoming one in constant time.
2. Why does Rabin-Karp verify with a direct character comparison after a hash match?
Different substrings can produce the same hash value, so a full comparison confirms a true match.
3. What is Rabin-Karp's worst-case time complexity?
With many hash collisions forcing repeated full verifications, the worst case degrades to O(n * m).
Flash Cards
What technique makes Rabin-Karp fast on average? — A rolling hash that updates each window in O(1) instead of rehashing from scratch.
Why still compare characters after a hash match in Rabin-Karp? — To rule out a hash collision (false positive) between different substrings.
What is Rabin-Karp's average-case time complexity? — O(n + m), where n is text length and m is pattern length.
When is Rabin-Karp especially useful compared to KMP? — When searching for many patterns at once, since all pattern hashes can be checked in one text scan.