Rabin-Karp String Matching

Rolling hashes for constant-time window screening

Compare fingerprints before characters

Rabin-Karp hashes the pattern and each text window of the same length. Unequal hashes prove the strings differ, so the window can be skipped immediately. Equal hashes are only a candidate match because different strings can collide.

Roll the hash as the window moves

A polynomial rolling hash removes the outgoing character's weighted contribution, shifts the remaining value by the base, and adds the incoming character. This updates the next window in O(1) time instead of hashing all m characters again.

The player scans abcabcab for cab. It displays the current window and both hashes. Hash equality triggers a character verification; successful verification records the starting index in green.

Hash pattern "cab" to 312, then begin with the first text window.

1function rabinKarp(text: string, pat: string): number[] {
const n = text.length, m = pat.length;
const B = 10, M = 997;
const val = (ch: string) => ch.charCodeAt(0) - 96;
let patHash = 0, winHash = 0, pow = 1;
for (let k = 0; k < m; k++) {
  patHash = (patHash * B + val(pat[k])) % M;   // pattern hash
  winHash = (winHash * B + val(text[k])) % M;  // first window hash
  if (k < m - 1) pow = (pow * B) % M;
}
const res: number[] = [];
for (let i = 0; i + m <= n; i++) {
  if (winHash === patHash) {                    // hash match
    if (text.slice(i, i + m) === pat) {         // verify characters
      res.push(i);
    }
  }
  if (i + m < n) {                              // rolling update O(1)
    winHash = ((winHash - val(text[i]) * pow) * B + val(text[i + m])) % M;
    winHash = ((winHash % M) + M) % M;
  }
}
return res;
24}

Text Tabcabcab

Pattern Pcab

Pattern hash312

Window hash123

Matches—

1 / 12

Expected linear time with a worst-case caveat

Initial hashes cost O(m) and the scan performs O(n) rolling updates. With rare collisions, expected time is O(n + m). Repeated collisions can force O(nm) character verification, so robust implementations use large moduli, randomized bases, or double hashing.

Hash equality is never accepted as proof. Character verification keeps the algorithm correct even when collisions occur.

Compare hash-based screening with prefix reuse in KMP String Matching, then explore palindrome symmetry in Manacher's algorithm.

Algorithm Visualizer

Rabin-Karp String Matching

Compare fingerprints before characters

Roll the hash as the window moves

Expected linear time with a worst-case caveat