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
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More