Rabin-Karp & Rolling Hash

The 10-second versionCopy Anchor Link

Rabin-Karp compares hashes instead of characters. Hash the pattern once; then slide an m-length window across the text, and — here's the trick — don't re-hash each window from scratch. Update the previous window's hash by removing the character that left and mixing in the character that arrived, both in O(1). When a window's hash equals the pattern's hash, verify by comparing characters to rule out collisions. Average O(n + m); worst case O(nm) if the hashes keep colliding. Its superpower: searching for many patterns at once.

Why this existedCopy Anchor Link

By the mid-1980s there were already deterministic linear-time matchers like KMP. So why bother? Two reasons.

First, comparing strings is expensive. If you want to know whether two long pieces of text are identical, comparing them character by character is O(length) — and in problems like multiple pattern matching, or matching a whole 2D picture, you do that comparison over and over. A short fingerprint — a number that (almost always) identifies a string — lets you rule out unequal things in a single integer comparison.

Second, KMP has to preprocess the pattern. For one pattern that's fine; for a thousand patterns it's a thousand preprocessings. If everyone shares a hash table instead, you can slide once and check all of them.

• 1981 — Michael Rabin introduces fingerprinting: map a string to a small number so that equal strings always get equal fingerprints, and unequal ones almost never do.
• 1987 — Richard Karp and Rabin publish "Efficient Randomized Pattern-Matching Algorithms," turning fingerprinting into a pattern matcher. Randomization is the price of admission — tiny collision odds buy a huge speedup.
• 1990s–2000s — rolling checksums of exactly this shape show up in rsync, in content-defined chunking for dedup systems, and in plagiarism detectors.

Why it mattered then: it reframed "are these strings equal?" as "are these numbers equal?" — an operation hardware does for free. That opened the door to searching for whole sets of patterns in one sweep, which is exactly what virus scanners and keyword engines needed.

Inside the inventor's headCopy Anchor Link

The setup is a sliding window of length m. As it moves one step right, it drops the leftmost character and gains a new one on the right:

The naive version hashes every window from scratch — O(m) per position, O(nm) total, no better than brute force. The pivot is noticing that the new window's hash can be derived from the old one. If the hash is the number you get by reading the window as a number in some base b, then sliding is just "subtract the leading digit's contribution, multiply the rest by b (shift left), and add the new digit." One subtraction, one multiply, one add.

Here is the trap. Fingerprints are finite; two different strings can share one — a collision. Rabin-Karp doesn't pretend otherwise. Every time the hashes agree, it stops and checks the characters. So a collision never produces a wrong answer; it only costs time. That's the whole trade: probabilistic speed, deterministic correctness.

And here's why the hash must be taken modulo a large prime: without it, the window's value grows without bound as m grows, and arithmetic on gigantic integers is slow. The modulus keeps every number machine-sized — at the cost of a few more collisions to verify.

// Naive: hash each window from scratch — O(m) per positionfunction windowHash(s, start, m) {  let h = 0;  for (let i = 0; i < m; i++)    h = (h * 256 + s.charCodeAt(start + i)) % 1_000_000_007;  return h;}// Rolling: reuse the previous hash — O(1) per slide//   h = ((h - s[i] * b^(m-1)) * b + s[i+m]) mod p

The final approachCopy Anchor Link

The hashCopy Anchor Link

Pick a base b (256 for bytes) and a large prime modulus p. The hash of a window c₀ c₁ … c_{m-1} is the polynomial

hash = c₀·b^(m-1) + c₁·b^(m-2) + … + c_{m-1}   (mod p)

which is just "the window read as a base-b number," folded into 0 … p-1.

The rolling updateCopy Anchor Link

The leading character's weight is b^(m-1); precompute it once (call it high). The update is th = (th - text[i] · high) · b + text[i+m], all modulo p.

The invariantsCopy Anchor Link

1. Hash agreement. After each slide, th equals the polynomial hash of the window text[i .. i+m-1], by construction.
2. Verification. A match is only reported when the hashes are equal and the raw characters are equal. Collisions can waste time, never correctness.
3. One pass, small state. The window slides strictly left to right, keeping only the current hash — so the auxiliary space is O(1) for a single pattern.

A worked traceCopy Anchor Link

Use base 10 and digits as characters, so the arithmetic is transparent. Text 3 1 4 1 5 9 2, window length 3, pattern 415:

Each transition is one subtract, one multiply, one add — O(1), no matter how long the window.

It in codeCopy Anchor Link

function rabinKarp(text, pat, base = 256, mod = 1_000_000_007) {  const n = text.length, m = pat.length;  if (m === 0) return 0;  if (m > n) return -1;  const code = (c) => c.charCodeAt(0);  let high = 1;                                // base^(m-1) mod mod  for (let i = 0; i < m - 1; i++) high = (high * base) % mod;  let ph = 0, th = 0;  for (let i = 0; i < m; i++) {    ph = (ph * base + code(pat[i])) % mod;    th = (th * base + code(text[i])) % mod;  }  for (let i = 0; i + m <= n; i++) {    if (ph === th && text.slice(i, i + m) === pat) return i;   // verify!    if (i + m < n) {      th = ((th - code(text[i]) * high) % mod + mod) % mod;    // drop leading      th = (th * base + code(text[i + m])) % mod;              // add trailing    }  }  return -1;}

ComplexityCopy Anchor Link

The worst case bites when hashes collide constantly — e.g. a text of all a's against a pattern of all a's, or an adversary who picks a text that collides on purpose. Averaged over a good random base, collisions are rare and the verification almost never runs.

Searching for many patternsCopy Anchor Link

This is where Rabin-Karp outshines KMP. Hash every pattern once, bucket them by length, then slide one window per distinct length, looking up the window's hash in the bucket:

function rabinKarpMany(text, patterns, base = 256, mod = 1_000_000_007) {  const code = (c) => c.charCodeAt(0);  const hashOf = (s) => {    let h = 0;    for (const ch of s) h = (h * base + code(ch)) % mod;    return h;  };  const byLen = new Map();               // length -> Map(hash -> [patterns])  for (const p of patterns) {    const bucket = byLen.get(p.length) ?? new Map();    const key = hashOf(p);    bucket.set(key, [...(bucket.get(key) ?? []), p]);    byLen.set(p.length, bucket);  }  const hits = [];  for (const [m, bucket] of byLen) {    if (m > text.length) continue;    let high = 1;    for (let i = 0; i < m - 1; i++) high = (high * base) % mod;    let th = 0;    for (let i = 0; i < m; i++) th = (th * base + code(text[i])) % mod;    for (let i = 0; i + m <= text.length; i++) {      const list = bucket.get(th);      if (list) {        const w = text.slice(i, i + m);        for (const p of list) if (p === w) hits.push([i, p]);  // verify      }      if (i + m < text.length) {        th = ((th - code(text[i]) * high) % mod + mod) % mod;        th = (th * base + code(text[i + m])) % mod;      }    }  }  return hits;}

Where you meet it todayCopy Anchor Link

• File sync and deduplication. rsync and content-defined chunking systems run a rolling checksum over a byte stream to find shared blocks without re-reading whole files.
• Plagiarism detection. Tools like MOSS fingerprint overlapping windows of a document and look for matching fingerprints across submissions — winnowing is Rabin-Karp's descendant.
• Multi-keyword scanning. Antivirus and intrusion-detection engines match thousands of signatures at once; hashing the signatures and sliding once is exactly this page's trick.
• Databases and caches. Rolling hashes give quick "is this value changed?" fingerprints for memoization and content addressing.

function firstRepeat(text, L, base = 256, mod = 1_000_000_007) {  const n = text.length, code = (c) => c.charCodeAt(0);  if (L === 0 || L > n) return -1;  let high = 1;  for (let i = 0; i < L - 1; i++) high = (high * base) % mod;  let h = 0;  for (let i = 0; i < L; i++) h = (h * base + code(text[i])) % mod;  const seen = new Map();                     // hash -> first index seen  for (let i = 0; i + L <= n; i++) {    const j = seen.get(h);    if (j !== undefined && text.slice(i, i + L) === text.slice(j, j + L)) return i;    if (j === undefined) seen.set(h, i);    if (i + L < n) {      h = ((h - code(text[i]) * high) % mod + mod) % mod;      h = (h * base + code(text[i + L])) % mod;    }  }  return -1;}

RecapCopy Anchor Link

• Rabin-Karp compares hashes, not characters, and updates the window hash in O(1) as the window slides — one character out, one in.
• The update is hash = (hash - leading · b^(m-1)) · b + incoming, all modulo a large prime.
• Every hash hit is verified. Collisions cost time, never correctness; the worst case is O(nm), the average is O(n + m).
• Its edge over KMP is multiple patterns: hash them all, bucket by length, and slide once per length — the idea behind dedup, sync, and signature scanners.

Next up: The Z-Algorithm — a third linear-time matcher, this one built entirely around prefix matching.