Rabin-Karp Algorithm
Hashing-based string matching algorithm
The Rabin-Karp algorithm is a string-matching algorithm that uses a rolling hash function to efficiently find occurrences of a pattern within a text by comparing hash values instead of characters directly.
Definition
The Rabin-Karp algorithm is a string-matching algorithm that uses a rolling hash function to efficiently find occurrences of a pattern within a text by comparing hash values instead of characters directly.
Overview
Rabin-Karp, developed by Michael Rabin and Richard Karp in 1987, computes a hash value for the pattern and for each equal-length substring (window) of the text, comparing hash values instead of doing a full character-by-character comparison at every position. Its key efficiency trick is the rolling hash: rather than recomputing a window's hash from scratch as it slides one position through the text, the algorithm updates the previous window's hash in constant time by removing the outgoing character's contribution and adding the incoming character's contribution, typically using a polynomial hash function evaluated modulo a large prime to limit collisions and overflow. Because different substrings can occasionally produce the same hash value (a collision), Rabin-Karp performs a full character-by-character verification whenever a hash match is found, to confirm it is a true match rather than a false positive. In the average case this makes the algorithm run in O(n + m) time, similar to KMP, but its worst-case time degrades to O(n*m) if many hash collisions occur (which a well-chosen hash function and modulus make rare in practice, though adversarial inputs can be crafted against a known fixed hash function). Rabin-Karp's rolling-hash technique generalizes naturally beyond single-pattern search to multi-pattern matching, since many pattern hashes can be checked against each window's hash using a set lookup, making it well suited to plagiarism detection systems that must check many documents' substrings against each other. It is also foundational to content-defined chunking used in deduplication and version-control systems (rolling hashes identify chunk boundaries in data streams), and is commonly used in coding interviews and competitive programming as an intuitive introduction to hashing-based string algorithms.
Key Concepts
- Uses a rolling hash to compare substring hashes instead of raw characters
- Updates each window's hash in constant time as it slides through the text
- Verifies hash matches with full character comparison to rule out collisions
- Averages O(n + m) time, though worst case can degrade to O(n*m)
- Developed by Michael Rabin and Richard Karp in 1987
- Naturally extends to multi-pattern search via hash set lookups
- Underlies content-defined chunking in deduplication systems
- Commonly used to teach hashing-based string algorithm design