Knuth-Morris-Pratt vs Rabin-Karp: What is the Difference?
Compare KMP and Rabin-Karp string matching, their time complexities, and how to answer this pattern-matching interview question.
Expected Interview Answer
KMP guarantees O(n + m) worst-case time by precomputing a failure function that avoids re-scanning matched characters after a mismatch, while Rabin-Karp uses rolling hashes to compare substrings in O(1) amortized time per position but degrades to O(nm) worst case on hash collisions.
KMP builds a prefix table over the pattern that tells the matcher, on a mismatch, how far to shift without re-examining characters it has already confirmed match. This gives a strict O(n + m) guarantee with no dependence on the alphabet or randomness. Rabin-Karp instead computes a rolling hash of every window of the text and compares it to the pattern hash, sliding the window in O(1) per step by removing the leaving character and adding the entering one arithmetically. Rabin-Karp shines when searching for many patterns at once, or in multi-pattern and plagiarism-detection settings, because the rolling hash generalizes cheaply, but it needs a verification step on hash matches and a well-chosen modulus to keep collisions rare.
- KMP gives a strict O(n + m) worst-case bound
- Rabin-Karp extends naturally to multi-pattern search
- KMP needs no hashing or collision handling
- Rabin-Karp rolling hash updates in O(1) per shift
AI Mentor Explanation
KMP is like a bowler who, after being read for four balls of an over then mis-timed on the fifth, does not restart their whole rhythm from scratch — the failure table tells them exactly which part of their run-up is still valid so they resume mid-sequence instead of re-running the full approach. Rabin-Karp is like a scorer who keeps a rolling fingerprint of the last six deliveries bowled, updating it in one arithmetic step as each new ball replaces the oldest, and only pulls out the full delivery log to double-check when that fingerprint matches a known pattern. The bowler analogy shows KMP never repeats work it already trusts, while the scorer analogy shows Rabin-Karp trades a cheap running summary for an occasional careful recheck. Both scan the same over, but one relies on structural memory and the other on a compact signature.
Step-by-Step Explanation
Step 1
Precompute the KMP failure table
For each pattern prefix, store the length of the longest proper prefix that is also a suffix.
Step 2
Scan with KMP using the table
On a mismatch, shift using the failure table instead of restarting the text pointer, giving O(n + m) total.
Step 3
Compute a rolling hash for Rabin-Karp
Hash the pattern and the first text window, then slide the window updating the hash in O(1) via modular arithmetic.
Step 4
Verify Rabin-Karp hash hits
On a hash match, compare the actual substring to the pattern to rule out a collision before accepting the match.
What Interviewer Expects
- State KMP is O(n + m) worst case, deterministic, no hashing needed
- State Rabin-Karp is O(n + m) average but O(nm) worst case on collisions
- Explain the failure function / prefix table concept correctly
- Explain the rolling hash update and why verification is required
Common Mistakes
- Claiming Rabin-Karp is always faster because hashing is O(1)
- Confusing the KMP failure table with a simple char-by-char lookup table
- Forgetting Rabin-Karp needs a verification step after a hash match
- Not knowing Rabin-Karp generalizes better to multi-pattern search
Best Answer (HR Friendly)
“KMP is a string-matching algorithm that never re-checks characters it already confirmed matched, so it always runs in linear time no matter the input. Rabin-Karp instead uses a rolling hash to quickly compare chunks of text to the pattern, which is usually fast and great for searching many patterns at once, but needs a verification step because hashes can occasionally collide.”
Code Example
def kmp_search(text, pattern):
if not pattern:
return []
fail = [0] * len(pattern)
k = 0
for i in range(1, len(pattern)):
while k > 0 and pattern[i] != pattern[k]:
k = fail[k - 1]
if pattern[i] == pattern[k]:
k += 1
fail[i] = k
matches = []
k = 0
for i, ch in enumerate(text):
while k > 0 and ch != pattern[k]:
k = fail[k - 1]
if ch == pattern[k]:
k += 1
if k == len(pattern):
matches.append(i - k + 1)
k = fail[k - 1]
return matches
def rabin_karp_search(text, pattern, base=256, mod=1_000_000_007):
n, m = len(text), len(pattern)
if m > n:
return []
high_order = pow(base, m - 1, mod)
pattern_hash = text_hash = 0
for i in range(m):
pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
text_hash = (text_hash * base + ord(text[i])) % mod
matches = []
for i in range(n - m + 1):
if text_hash == pattern_hash and text[i:i + m] == pattern:
matches.append(i)
if i < n - m:
text_hash = ((text_hash - ord(text[i]) * high_order) * base + ord(text[i + m])) % mod
return matchesFollow-up Questions
- How would you extend Rabin-Karp to search for multiple patterns at once?
- Why is the KMP failure table also called the longest proper prefix-suffix array?
- How would you pick a hash base and modulus to minimize Rabin-Karp collisions?
- When would you prefer the Z-algorithm over both KMP and Rabin-Karp?
MCQ Practice
1. What is the worst-case time complexity of KMP string matching?
KMP guarantees O(n + m) worst case by never re-examining already matched characters, using the precomputed failure table.
2. Why does Rabin-Karp need to verify a match after a hash collision?
Hash collisions mean two different substrings can produce the same hash value, so the algorithm must confirm with a direct comparison.
3. What does the KMP failure table store for each prefix of the pattern?
The failure table records, for each prefix, how much can be reused as a new match start after a mismatch, avoiding redundant re-scanning.
Flash Cards
What is KMP’s worst-case time complexity? — O(n + m), guaranteed, using the precomputed failure table.
What does Rabin-Karp use to compare substrings quickly? — A rolling hash updated in O(1) per shift, verified by direct comparison on a hash match.
What is Rabin-Karp’s worst-case time complexity? — O(nm), when many hash collisions force repeated full comparisons.
Which algorithm generalizes better to multi-pattern search? — Rabin-Karp, since rolling hashes can be checked against a set of pattern hashes cheaply.