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.
Fingerprint equal-length windows
Choose a base that represents the alphabet and a modulus that keeps numbers bounded. Compute the pattern hash and the first M-character window. A different hash proves the strings differ; an equal hash only suggests they might match.
This filter is useful because most windows are rejected with integer arithmetic rather than M character comparisons. The algorithm becomes incorrect if it reports hash equality without verifying the characters.
- Hash inequality safely rejects
- Hash equality needs verification
- Modulo bounds arithmetic
Rolling in constant time
To shift one position, remove the outgoing character's contribution at the highest power, multiply the remainder by the base, and add the incoming character. Precompute base^(M−1) modulo q so removal is O(1).
Normalize a negative modular result before continuing. Languages differ in how remainder handles negative operands; adding the modulus before taking remainder prevents the same window from receiving inconsistent fingerprints.
- Remove outgoing contribution
- Shift and add incoming character
- Normalize negative residues
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");}}text CABABA; pattern ABAMatch index: 1Run the example step by step
Collisions and complexity
A collision is two unequal strings with the same hash. Exact verification makes collisions affect speed but never correctness. With a well-chosen modulus, expected time is O(N+M); adversarial or unlucky collisions can force O(NM).
Double hashing lowers collision probability but does not replace verification when an exact answer is required. Randomizing the base or modulus can make adversarial construction harder, while cryptographic hashes are usually unnecessary overhead for substring search.
- Collisions are unavoidable in finite hashes
- Verification gives exact answers
- Worst case remains quadratic
Where Rabin–Karp is strongest
Rolling hashes generalize naturally to finding many patterns of one length, detecting duplicate substrings, and comparing substrings after prefix-hash preprocessing. KMP instead preprocesses one pattern and provides deterministic linear matching.
For Unicode text, hash code points or normalized units consistently rather than assuming one byte per character. For an empty pattern or M>N, handle the boundary before computing the first window.
- Useful for multiple equal-length patterns
- Prefix hashes compare substrings
- Character representation must be consistent
Common implementation failures
Forgetting the highest-power multiplier removes the wrong positional value. Rolling before checking the current window skips position zero, while rolling after the final window reads beyond the text. Write the loop around explicit window start indexes.
A small modulus or additive hash creates frequent collisions. More importantly, never claim rolling makes the entire search worst-case O(N): only each hash shift is O(1); collision verification can still inspect M characters.
- Check before shifting
- Stop after the final window
- Expected and worst-case bounds differ
Building a trustworthy rolling-hash API
Precompute the high power with the same modular arithmetic used by the window hash, and keep the character mapping stable between pattern and text. At every window start, compare hashes before rolling. If they match, verify the exact substring character by character; only that verification may return a match. After the final window, stop without reading an incoming character beyond the text.
Test a match at position zero, a match in the final window, M greater than N, repeated characters, and a deliberately tiny modulus that causes a collision. The collision case is essential because it proves the implementation verifies rather than trusting the fingerprint. For many queries over one text, prefix hashes may be more appropriate; for one exact pattern with a deterministic worst-case guarantee, prefer KMP.
When returning every occurrence, continue to the next window after verification rather than stopping at the first candidate. Record both hash comparisons and character verifications in performance measurements so a poor modulus cannot hide behind an apparently constant-time rolling loop. Keep window boundaries explicit in those measurements.
- Use one character encoding consistently
- Verify every hash candidate
- Collision tests protect correctness