Rabin-Karp

Strings O(n + m) avg O(1)

Hashes the pattern and each text window with a rolling hash, verifying character-by-character only when hashes collide.

text

E10

K11

S12

pattern

TextPattern

patHash=22052winHash=22052

1/31

Precompute pattern hash and hash of the first window.

InvariantThe window hash equals the hash of those m characters. Equal hashes may still differ, so a hit is verified; differing hashes never can, so a miss is free.

pointermatchmismatchwindow

rabin-karp.c

#define BASE 256
#define MOD 1000000007
 
void rabinKarp(const char *t, const char *p) {
    int n = strlen(t), m = strlen(p);
    long ph = 0, th = 0, pow = 1;
    for (int i = 0; i < m; i++) {
        ph = (ph * BASE + p[i]) % MOD;
        th = (th * BASE + t[i]) % MOD;
        if (i) pow = (pow * BASE) % MOD;
    }
    for (int i = 0; i + m <= n; i++) {
        if (ph == th) {
            int k = 0;
            while (k < m && t[i + k] == p[k]) k++;
            if (k == m) printf("found at %d\n", i);
        }
        if (i + m < n) {
            th = ((th - t[i] * pow) * BASE
                  + t[i + m]) % MOD;
            if (th < 0) th += MOD;
        }
    }
}

How Rabin-Karp works

Compare hashes, not strings: a rolling hash updates the window's value in O(1) as it slides. Only hash collisions trigger a real character-by-character check.

Best case

Few collisions: O(n + m) expected.

Worst case

Adversarial collisions: O(n·m).

When to use it

Multi-pattern search (one hash set, many patterns), plagiarism chunk matching.