Rabin–Karp — Rolling Hash Pattern Matching

What does it solve?

Find occurrences of a pattern P in text T by comparing hashes instead of characters. Compute the pattern's hash once, then slide a window over the text keeping a running hash.

Key insight: a rolling hash updates in O(1): drop the leaving character's contribution, shift, add the entering one. When a window hash equals the pattern hash it's a candidate, verify character-by-character to rule out a spurious hit (a hash collision). Average cost is O(N + M); worst case O(N·M) if everything collides.

The core idea

// polynomial rolling hash, base b, mod q
h(w) = (w0·b^(m-1) + … + w_{m-1}) mod q
// roll the window one step right:
roll = ( (h − T[i]·b^(m-1))·b
+ T[i+m] ) mod q

Complexity

Time complexity

O(N + M)

Average case with a good hash. Each roll is O(1); verification is rare. Worst case O(N·M) when hashes collide on every window.

Space complexity

O(1)

Just the two hashes, the high-order multiplier b^(m-1), and a few counters. No table proportional to input size.

Examples & edge cases

Live animation — rolling the window hash across the text

current window char leaving char entering hash hit → verify confirmed occurrence

Text — window of width |P| = —

Hash comparison — window vs pattern (base 26, mod 101)

window hash

—

pattern hash

—

Press Play to compute the first window hash…

window = — patHash = — winHash = — matches = —

Step — of —

window start

—

index in text

window hash

—

rolling value

hash hits

—

candidates

matches found

—

verified

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	Phase	start	window	winHash	patHash	Hash eq?	Verify	Matches

C++ implementation

rabin_karp.cpp

#include <bits/stdc++.h>
using namespace std;

// Rabin-Karp: return all start indices of p in t
vector<int> rabinKarp(const string& t, const string& p) {
    const long long b = 26, q = 101;   // base and a prime modulus
    int n = t.size(), m = p.size();
    vector<int> res;
    if (m > n || m == 0) return res;

    long long h = 1;                    // b^(m-1) % q, the high-order weight
    for (int i = 0; i < m - 1; i++) h = (h * b) % q;

    long long ph = 0, wh = 0;         // pattern hash, window hash
    for (int i = 0; i < m; i++) {
        ph = (b * ph + p[i]) % q;
        wh = (b * wh + t[i]) % q;
    }

    for (int s = 0; s <= n - m; s++) {
        if (ph == wh) {               // hashes agree → candidate
            if (t.compare(s, m, p) == 0) // verify char-by-char
                res.push_back(s);
        }
        if (s < n - m) {              // roll to the next window
            wh = (b * (wh - t[s] * h) + t[s + m]) % q;
            if (wh < 0) wh += q;       // keep it non-negative
        }
    }
    return res;
}

int main() {
    auto hits = rabinKarp("ABCCDABCAB", "ABC");
    for (int x : hits) cout << x << " "; // 0 5
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars