Rabin–Karp Algorithm
Rabin–Karp fingerprints the pattern and each equally sized text window. Hash inequality rejects a window immediately; hash equality triggers an exact comparison because different strings can collide.
Fingerprints Instead of Comparisons
Naive string matching compares the pattern against every window of the text character by character, at O(n · m). Rabin–Karp replaces most of those comparisons with a single integer test.
The idea is to compute a hash of the pattern once, then a hash of each length-m window of the text, and compare numbers rather than strings. Two different strings almost always hash differently, so a hash mismatch rules out a match in O(1) instead of up to O(m).
On its own that would not help — hashing each window from scratch costs O(m), giving the same O(n·m). The algorithm works because of a second idea: consecutive windows overlap in all but two characters, so the next window's hash can be derived from the current one in constant time rather than recomputed. That is the rolling hash.
The asymmetry that makes the whole thing sound is the same one behind bloom filters. Different hashes prove the strings differ; equal hashes prove nothing. So a hash match must be followed by an actual character-by-character comparison to confirm it.
A hash match on strings that are not equal is a spurious hit or false positive. With a well-chosen hash these are rare, so the expensive verification runs rarely, and the expected cost is O(n + m).
- Hash the pattern once, then hash each window of the text
- Consecutive windows share m−1 characters, so the hash can be updated
- A hash mismatch rules out a match in O(1)
- A hash match must always be verified character by character
Rolling in Constant Time
The standard choice is a polynomial rolling hash, treating the string as a number in some base. For a window s[0..m-1], the hash is s[0]·b^(m−1) + s[1]·b^(m−2) + … + s[m−1], all taken modulo a large prime.
The base b should exceed the alphabet size — 31, 256 or 257 are common — and the modulus should be a large prime, typically around 10⁹, chosen so that intermediate products still fit in a 64-bit integer.
Rolling from one window to the next takes three steps. Remove the outgoing character by subtracting s[i] · b^(m−1). Shift the remaining value by multiplying by b. Add the incoming character. Every operation is modular, and the value b^(m−1) mod p is precomputed once so the removal is a single multiplication.
Two implementation details cause most of the bugs.
Negative intermediates. After the subtraction the value may go negative in languages where % follows the sign of the dividend — C, C++, Java. The fix is ((x % p) + p) % p, and omitting it produces sporadic missed matches that are genuinely hard to trace. Python's % always returns a non-negative result, so the issue does not arise there.
Overflow. Multiplying two values near 10⁹ produces something near 10¹⁸, which fits in a signed 64-bit integer but not a 32-bit one. Using int in C++ or Java where long is required silently wraps and corrupts every subsequent hash.
The modulus is also where the algorithm's robustness lives. A small modulus makes collisions frequent and the verification step common, degrading performance toward O(n·m). A fixed, publicly known modulus and base allow an adversary to construct inputs that collide deliberately — so security-sensitive uses randomise the base at runtime.
- Hash a window as a polynomial in a base, modulo a large prime
- Roll by subtracting the old term, multiplying by the base, adding the new
- Normalise with
((x % p) + p) % p— negative intermediates are a real bug - Use 64-bit arithmetic; a near-10⁹ modulus overflows 32 bits when multiplied
Collisions and the Two Complexities
The complexity has to be quoted with its case, because the gap between them is the whole story.
Expected O(n + m): computing the initial hashes is O(m), rolling through the text is O(n), and with a good hash the number of spurious hits is small enough that verification adds only a constant factor overall.
Worst case O(n · m): if every window's hash collides with the pattern's, every position triggers a full O(m) verification. With a fixed base and modulus this is constructible — an adversary who knows the parameters can generate text producing collisions everywhere.
The defence is randomising the base at program start. An attacker cannot then predict which strings collide, and the expected bound holds regardless of input. This mirrors the hash-flooding defence used by language runtimes for their hash tables.
An alternative that removes verification almost entirely is double hashing: maintain two independent rolling hashes with different bases and moduli, and treat a match as genuine only when both agree. The probability of a simultaneous collision drops to roughly the product of the individual rates — around 10⁻¹⁸ with two 10⁹ moduli — which is low enough that many competitive programming solutions skip the character-by-character check altogether. That is a deliberate probabilistic trade rather than a correct algorithm, and it should be stated as such.
Note the difference in guarantee from KMP, which is O(n + m) in the worst case with no randomisation and no verification. Where a hard bound is required, KMP is the safer choice — Rabin–Karp's appeal lies elsewhere.
| Rabin–Karp | KMP | Boyer–Moore | |
|---|---|---|---|
| Expected | O(n + m) | O(n + m) | Sublinear in practice |
| Worst case | O(n·m) | O(n + m) | O(n·m) |
| Extra space | O(1) | O(m) | O(alphabet) |
| Many patterns | One pass, shared hash | No | No |
| 2-D matching | Natural | Awkward | Awkward |
- Expected O(n + m); worst case O(n · m) when collisions are frequent
- A fixed base and modulus make the worst case constructible
- Randomise the base to restore the expected bound
- Double hashing makes collisions negligible but is still probabilistic
Roll a pattern hash across the text
def rabin_karp(text, pattern, base=256, mod=101):
m = len(pattern)
high = pow(base, m - 1, mod)
pattern_hash = 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
for start in range(len(text) - m + 1):
if pattern_hash == window_hash and text[start:
start + m] == pattern:
return start
if start < len(text) - m:
window_hash = ((window_hash - ord(text[start]) * high) * base + ord(text[start + m])) % mod
return -1
print("Match index:", rabin_karp("CABABA", "ABA"))#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main() {
string t="CABABA",p="ABA";
int b=256,q=101,m=p.size(),h=1,ph=0,wh=0;
for(int i=1;i<m;i++)h=h*b%q;
for(int i=0;i<m;i++) {
ph=(ph*b+p[i])%q;
wh=(wh*b+t[i])%q;
}
for(int s=0;s+m<=t.size();s++) {
if(ph==wh&&t.compare(s,m,p)==0) {
cout<<"Match index: "<<s;
return 0;
}
if(s+m<t.size())wh=((wh-t[s]*h)%q+q)%q*b%q+t[s+m],wh%=q;
}
cout<<"Match index: -1";
}class Main {
public static void main(String[]z) {
String t="CABABA",p="ABA";
int b=256,q=101,m=p.length(),h=1,ph=0,wh=0;
for(int i=1;i<m;i++)h=h*b%q;
for(int i=0;i<m;i++) {
ph=(ph*b+p.charAt(i))%q;
wh=(wh*b+t.charAt(i))%q;
}
for(int s=0;s+m<=t.length();s++) {
if(ph==wh&&t.regionMatches(s,p,0,m)) {
System.out.print("Match index: "+s);
return;
}
if(s+m<t.length()) {
wh=((wh-t.charAt(s)*h)%q+q)%q;
wh=(wh*b+t.charAt(s+m))%q;
}
}
System.out.print("Match index: -1");
}
}Step through it
Running on text CABABA; pattern ABA
Read all 12 Steps
- Choose base and modulus Use base 256 and modulus 101.
- Hash pattern Compute ABA from left to right.
- Hash first window Compute CAB with the same positional rule.
- Compare CAB Different hashes safely reject start 0.
- Remove outgoing C Subtract C times the highest base power.
- Shift and add B Multiply the remainder and add incoming B.
- Hash candidate ABA The window at start 1 is ABA.
- Hashes agree Equal hashes create a candidate, not proof.
- Verify A Compare the first characters.
- Verify B Compare the middle characters.
- Verify final A Compare the last characters; collision verification succeeds.
- Report exact match Return start index 1.
Where It Beats the Alternatives
For finding one pattern, KMP is generally the better choice — same expected cost, a real worst-case guarantee, no arithmetic pitfalls. Rabin–Karp earns its place in three situations that the others handle poorly or not at all.
Many patterns at once. To search for k patterns of the same length, hash all of them into a set, then roll a single hash across the text and check membership at each position. That is O(n + k·m) — one pass over the text regardless of how many patterns there are. KMP would need k separate passes or the more complex Aho–Corasick machinery.
This is exactly what plagiarism detection does: hash every fixed-length substring of every source document, then roll across the candidate text looking for hits. The Rabin fingerprint used in file deduplication and rsync's delta encoding is the same idea applied to binary blocks.
Two-dimensional matching. To find an r × c pattern in a grid, hash each row of the pattern, then hash each row-window of the grid, reducing the problem to matching a sequence of r hashes — a 1-D problem on hash values. Rolling works in both directions. The other algorithms do not extend nearly so cleanly.
Substring problems generally. Once a rolling hash exists, comparing any two substrings of a text becomes O(1) after O(n) precomputation of prefix hashes. That turns a family of otherwise-hard problems into simple ones: the longest common substring via binary search on length, the longest repeated substring, palindrome testing on arbitrary ranges, and duplicate-substring detection.
That last use is arguably more important than the string search the algorithm is named for. A precomputed prefix-hash array is a standard tool, and Rabin–Karp is where the technique comes from.
One practical warning for all of these: always verify on a hash match unless you have deliberately accepted a probabilistic answer with double hashing, and can state the error probability if asked.
- k patterns of one length cost O(n + k·m) — a single pass over the text
- 2-D matching reduces to 1-D matching on row hashes
- Prefix hashes compare any two substrings in O(1) after O(n) setup
- Used in plagiarism detection, rsync, and file deduplication