Rabin-Karp Algorithm from Scratch (2026)
Rabin-Karp is a string matching algorithm that uses rolling hash to compare the pattern with text substrings in O(n+m) average time. It computes hash values for the pattern and every substring of length m, sliding one character at a time.
While worst-case complexity is O(n*m) due to hash collisions, careful hash function design makes collisions rare, giving linear expected performance.
Rolling Hash Function
The rolling hash treats the pattern as a base-d number modulo a large prime. When sliding the window, the hash is updated in O(1) by subtracting the contribution of the outgoing character and adding the new character, multiplying by the base.
A common choice is base 256 (extended ASCII) with a large prime like 10^9+7, though base 26 suffices for lowercase letters.
const long long BASE = 256, MOD = 1e9 + 7;
long long modPow(long long a, long long b) {
long long res = 1;
while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; }
return res;
}
long long rollingHash(string& s, int start, int end) {
long long hash = 0;
for (int i = start; i < end; i++)
hash = (hash * BASE + s[i]) % MOD;
return hash;
}Rabin-Karp Matching
Compute target hash for the pattern and initial window hash for text[0..m-1]. Slide through the text, comparing hashes. When hashes match, verify character-by-character to avoid false positives from collisions.
The rolling update eliminates the O(m) per window recomputation, achieving O(n) average time for non-pathological inputs.
vector rabinKarp(string& text, string& pattern) {
int n = text.size(), m = pattern.size();
if (m > n) return {};
long long pow = modPow(BASE, m - 1);
long long patHash = rollingHash(pattern, 0, m);
long long txtHash = rollingHash(text, 0, m);
vector matches;
for (int i = 0; i <= n - m; i++) {
if (txtHash == patHash) {
bool match = true;
for (int j = 0; j < m; j++)
if (text[i + j] != pattern[j]) { match = false; break; }
if (match) matches.push_back(i);
}
if (i < n - m) {
txtHash = (txtHash - text[i] * pow % MOD + MOD) % MOD;
txtHash = (txtHash * BASE + text[i + m]) % MOD;
}
}
return matches;
} Frequently Asked Questions
What is a rolling hash?
A rolling hash computes hash values for sliding substrings in O(1) per shift by updating the previous hash: removing the leftmost character's contribution and appending the new rightmost character, leveraging modular arithmetic.
Why verify character-by-character after hash match?
Hash collisions (different strings with the same hash modulo prime) can produce false positives. Character-by-character verification ensures correctness, and with a good hash function, collisions are rare in practice.
Originally published on Ayodhyyya. Last updated June 1, 2026.