Introduction
The Rabin-Karp algorithm finds occurrences of a pattern in a text by comparing hash values of substrings instead of comparing characters directly at every position. It computes a hash of the pattern and a hash of each length-m window of the text, using a rolling hash that can be updated in O(1) when the window slides by one character. When hashes match, it verifies with a direct character comparison to guard against hash collisions.
Cricket analogy: Instead of checking every ball-by-ball sequence character by character for a repeated bowling pattern, Rabin-Karp computes a quick hash 'signature' for each 6-ball window and only does a detailed replay check when signatures match, guarding against a coincidental hash collision.
Algorithm/Syntax
def rabin_karp_search(text: str, pattern: str, base: int = 256, mod: int = 1_000_000_007) -> list[int]:
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:
if text[i:i + m] == pattern: # verify to rule out collisions
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 matchesExplanation
Each substring of length m is treated as a number in a given base (e.g. 256 for byte values), reduced modulo a large prime to keep values bounded. The rolling hash update removes the contribution of the outgoing character (text[i] * base^(m-1)) and adds the incoming character (text[i+m]), all in O(1), rather than recomputing the hash of the whole window from scratch. Because different substrings can occasionally hash to the same value (a collision), Rabin-Karp always verifies a hash match with an explicit character-by-character comparison before accepting it as a true match; this keeps the algorithm correct while the hashing keeps it fast on average.
Cricket analogy: Treating each 6-ball window as a number in a numeral system and reducing it modulo a large prime keeps the hash bounded; sliding to the next window just removes the outgoing ball's contribution and adds the incoming ball's, an O(1) rolling update instead of re-hashing all 6 balls from scratch.
Example
text = "abxabcabcaby"
pattern = "abc"
result = rabin_karp_search(text, pattern)
print("Matches at indices:", result) # [4, 7]
# Trace (base=256, small mod for illustration only):
# window 'abx' -> hash H1
# window 'abc' (shift by 1) -> hash updated in O(1) using rolling formula
# hash of 'abc' pattern matches window at index 4 and index 7 -> verified equal -> recordedComplexity
Average and best case time is O(n+m): O(m) to compute the initial pattern and window hashes, and O(n-m) rolling updates each costing O(1), plus verification that is cheap on average because collisions are rare with a good modulus. Worst case, if many spurious hash collisions occur (or an adversarial input/modulus is chosen), each verification can cost O(m), giving O(n*m) worst case. Using a large prime modulus and, optionally, double hashing, makes worst-case collisions extremely unlikely in practice. Space is O(1) beyond the input.
Cricket analogy: On average, scanning a full season's ball-by-ball log for a specific bowling pattern of length m takes O(n+m) with Rabin-Karp's rolling hash, but an adversarial sequence causing many hash collisions could degrade to O(n*m); using a large prime modulus, like choosing a bigger boundary rope, makes that worst case rare, and needs no extra scoreboard space beyond the log.
Key Takeaways
- Rabin-Karp compares hash values of substrings instead of raw characters, updating the hash in O(1) as the window slides (rolling hash).
- A hash match must always be verified with a direct string comparison to rule out collisions.
- Average/best-case time is O(n+m); worst case degrades to O(n*m) under heavy hash collisions.
- It generalizes well to searching for multiple patterns simultaneously by comparing against a set of pattern hashes.
Practice what you learned
1. What is the key data structure/technique that makes Rabin-Karp efficient?
2. Why does Rabin-Karp verify a match with a direct character comparison even after the hashes match?
3. What is the average-case time complexity of Rabin-Karp?
4. In the rolling hash update, what must be subtracted out when the window slides forward by one character?
5. What causes Rabin-Karp's worst-case time to degrade to O(n*m)?
Was this page helpful?
You May Also Like
Naive String Matching and KMP
Compare brute-force substring search with the Knuth-Morris-Pratt algorithm, which uses a failure function to avoid re-scanning characters.
Trie-Based String Algorithms
Learn how a trie (prefix tree) organizes strings for fast insertion, search, and prefix queries.
Algorithm Complexity Cheat Sheet
A reference summary of time and space complexities for the major algorithms covered in this course.