Introduction

Imagine you need to find the word "needle" inside a document that is millions of characters long. The simplest approach — check every position, compare the pattern character by character — works, but it can examine each character of the text m times (once for each of the m characters in the pattern), giving O(n⋅m)O(n \cdot m) work in the worst case.

Michael Rabin and Richard Karp published a better idea in 1987: instead of comparing characters directly, compute a fingerprint (a hash) of the pattern and slide a matching-size window across the text. At each position you compare two integers rather than up to m characters. The trick is making the window slide in O(1)O(1) per step — by updating the hash algebraically rather than recomputing it from scratch.

The resulting algorithm finds any pattern in O(n)O(n) time on average, and it extends naturally to searching for multiple patterns at once — something that beats even the Knuth-Morris-Pratt automaton at scale. It is one of the cleanest examples in computer science of turning a comparison problem into an arithmetic one.

Watch the Hash Slide

Type a pattern and a text below, then step through the search one position at a time. The colored window shows the current window; the hash bar shows the pattern hash and the current window hash. When they match, the algorithm does a full character comparison to rule out false positives.

<div class="controls">
  <label>Pattern: <input id="pat" type="text" value="abc" maxlength="12" /></label>
  <label>Text: <input id="txt" type="text" value="xabcyabcz" maxlength="40" /></label>
</div>
<div class="hash-row">
  <span class="label">Pattern hash:</span>
  <span id="phash" class="hashval">—</span>
  <span class="label" style="margin-left:1.2rem">Window hash:</span>
  <span id="whash" class="hashval">—</span>
</div>
<div id="display" class="text-display"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btnPrev" type="button" class="ghost">← Prev</button>
  <button id="btnNext" type="button">Next →</button>
  <button id="btnAuto" type="button">Auto-run</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div id="matches" class="matches"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; margin-bottom: .7rem; }
.controls label { font-size: .88rem; font-weight: 600; color: #444; display: flex; align-items: center; gap: .35rem; }
input[type=text] { font: 15px ui-monospace, monospace; padding: .28rem .55rem; border: 1px solid #bbb; border-radius: 6px; width: 10rem; }
.hash-row { display: flex; align-items: center; gap: .4rem; font-size: .85rem; margin-bottom: .55rem; flex-wrap: wrap; }
.label { color: #555; font-weight: 600; }
.hashval { font: 700 15px ui-monospace, monospace; background: #eef1f5; border-radius: 5px; padding: .15rem .5rem; min-width: 4rem; text-align: center; }
.hashval.match { background: #d4edda; color: #0a7d33; }
.hashval.nomatch { background: #fce8e8; color: #b91c1c; }
.text-display { display: flex; flex-wrap: wrap; gap: 3px; margin: .4rem 0; min-height: 2.6rem; }
.ch { display: inline-flex; align-items: center; justify-content: center;
      width: 30px; height: 34px; border-radius: 6px; font: 700 16px ui-monospace, monospace;
      background: #e8eef3; border: 1px solid #cdd9e3; color: #334; transition: background .15s; }
.ch.window { background: #ddeeff; border-color: #4a90d9; color: #1d3557; }
.ch.found { background: #d4edda; border-color: #28a745; color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.collision { color: #b45309; }
.status.nomatch { color: #888; }
.btns { display: flex; gap: .45rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.matches { margin-top: .55rem; font-size: .88rem; color: #444; min-height: 1.2em; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Rabin-Karp rolling hash demo.
// Hash: H = (c[0]*b^(m-1) + c[1]*b^(m-2) + ... + c[m-1]) mod q
// Roll: H_new = (b * (H_old - c[i]*b^(m-1)) + c[i+m]) mod q
const BASE = 31, MOD = 1000003;

function charCode(c) { return c.charCodeAt(0); }

function buildHash(s, len) {
  let h = 0, pw = 1;
  for (let i = 0; i < len; i++) {
    h = (h * BASE + charCode(s[i])) % MOD;
    if (i < len - 1) pw = pw * BASE % MOD;
  }
  return { h, pw };
}

function rollHash(oldH, outChar, inChar, pw) {
  let h = (BASE * (oldH - charCode(outChar) * pw % MOD + MOD) + charCode(inChar)) % MOD;
  return ((h % MOD) + MOD) % MOD;
}

let pos = 0, patHash = 0, winHash = 0, power = 1;
let pat = '', txt = '', m = 0, n = 0, foundAt = [];
let autoTimer = null;

function init() {
  pat = document.getElementById('pat').value;
  txt = document.getElementById('txt').value;
  m = pat.length; n = txt.length;
  pos = 0; foundAt = [];
  clearAuto();
  if (m === 0 || m > n) {
    document.getElementById('display').innerHTML = '';
    document.getElementById('status').textContent = m > n ? 'Pattern longer than text.' : 'Enter a pattern.';
    document.getElementById('status').className = 'status nomatch';
    document.getElementById('phash').textContent = '—';
    document.getElementById('whash').textContent = '—';
    document.getElementById('matches').textContent = '';
    return false;
  }
  const ph = buildHash(pat, m);
  patHash = ph.h; power = ph.pw;
  winHash = buildHash(txt, m).h;
  render();
  return true;
}

function render() {
  // Display
  const disp = document.getElementById('display');
  disp.innerHTML = '';
  for (let i = 0; i < n; i++) {
    const span = document.createElement('span');
    span.className = 'ch';
    span.textContent = txt[i];
    if (foundAt.includes(i)) span.classList.add('found');
    else if (i >= pos && i < pos + m) span.classList.add('window');
    disp.appendChild(span);
  }

  // Hash display
  const ph = document.getElementById('phash');
  const wh = document.getElementById('whash');
  ph.textContent = patHash;
  wh.textContent = winHash;
  const hashMatch = patHash === winHash;
  ph.className = 'hashval ' + (hashMatch ? 'match' : 'nomatch');
  wh.className = 'hashval ' + (hashMatch ? 'match' : 'nomatch');

  // Status
  const st = document.getElementById('status');
  const window_str = txt.slice(pos, pos + m);
  if (hashMatch) {
    if (window_str === pat) {
      st.textContent = fmt('✓ Hash match AND strings match at position %pos%!', { pos: pos });
      st.className = 'status ok';
    } else {
      st.textContent = fmt('⚡ Hash collision at position %pos%: hashes match but strings differ.', { pos: pos });
      st.className = 'status collision';
    }
  } else {
    st.textContent = fmt('Position %pos%: hash mismatch — skip (O(1) cost).', { pos: pos });
    st.className = 'status nomatch';
  }

  // Matches summary
  const done = pos + m >= n;
  document.getElementById('matches').textContent =
    foundAt.length > 0
      ? fmt('Found at position(s): %foundAt%.%v%', { foundAt: foundAt.join(', '), v: done ? ' Search complete.' : '' })
      : done ? 'No matches found.' : '';

  document.getElementById('btnPrev').disabled = pos === 0;
  document.getElementById('btnNext').disabled = pos + m >= n;
}

function step() {
  if (pos + m >= n) return;
  // Check current window for match
  const window_str = txt.slice(pos, pos + m);
  if (patHash === winHash && window_str === pat && !foundAt.includes(pos)) {
    foundAt.push(pos);
  }
  // Roll hash
  winHash = rollHash(winHash, txt[pos], txt[pos + m], power);
  pos++;
  render();
}

function stepBack() {
  if (pos === 0) return;
  // Recompute from scratch for simplicity in reverse
  pos--;
  winHash = buildHash(txt.slice(pos, pos + m), m).h;
  foundAt = foundAt.filter(p => p < pos);
  render();
}

function clearAuto() {
  if (autoTimer) { clearInterval(autoTimer); autoTimer = null; }
  document.getElementById('btnAuto').textContent = 'Auto-run';
}

document.getElementById('pat').addEventListener('input', init);
document.getElementById('txt').addEventListener('input', init);
document.getElementById('btnNext').addEventListener('click', () => { clearAuto(); step(); });
document.getElementById('btnPrev').addEventListener('click', () => { clearAuto(); stepBack(); });
document.getElementById('btnReset').addEventListener('click', () => { clearAuto(); init(); });
document.getElementById('btnAuto').addEventListener('click', () => {
  if (autoTimer) { clearAuto(); return; }
  document.getElementById('btnAuto').textContent = 'Pause';
  autoTimer = setInterval(() => {
    if (pos + m >= n) { clearAuto(); return; }
    step();
  }, 500);
});

init();
Result
Console

Notice how the hash updates without looking at all m characters — only the outgoing character is subtracted and the incoming character is added. A hash collision (equal hashes, unequal strings) triggers the safety check; in practice, with a good base and modulus, collisions are rare.

The Real Complexity

Rabin-Karp belongs to the solved family of string-search algorithms — its average-case bound is proven and tight. Here is the full picture:

  • Preprocessing: compute the pattern hash in O(m)O(m) time. Compute the base-power term bm−1 mod qb^{m-1} \bmod q used to drop the outgoing character.
  • Sliding: each of the n−m+1 positions costs O(1)O(1) to update the rolling hash: new_hash = (base * (old_hash − text[i] * power) + text[i+m]) mod q.
  • Average case: O(n+m)O(n + m). With a random prime modulus q, the probability that a non-matching window produces a spurious hash match is ≤ m/q — negligibly small for a large prime.
  • Worst case: O(nm)O(nm). If every window is a false positive (e.g., text = "aaa…a", pattern = "aaa…b"), each position triggers an O(m)O(m) character check. In practice this never happens with a randomized modulus; choosing q uniformly at random from a set of primes turns Rabin-Karp into a Las Vegas algorithm with expected O(n+m)O(n+m) and failure probability that falls off exponentially.
  • Multiple patterns: hash all k patterns into a hash set; each window check is O(1)O(1) expected lookup. Total time: O(n + m·k + occurrences). No other classical algorithm matches this.

Compare with pattern matching automata (KMP, Aho-Corasick): they guarantee O(n+m)O(n+m) worst case but require O(m·Σ) preprocessing for Aho-Corasick. Rabin-Karp trades the worst-case guarantee for dramatically simpler code and multi-pattern power.

Where It Matters

"Find this pattern in a long text" is one of the most common operations in computing, and Rabin-Karp's rolling hash shows up in surprising places:

  • Plagiarism and duplicate detection: tools like MOSS (Measure Of Software Similarity) fingerprint k-grams of source code with rolling hashes and compare fingerprint sets — a direct descendant of the Rabin-Karp idea.
  • Network intrusion detection: systems like Snort must match thousands of signatures against every packet. Rabin-Karp's multi-pattern strength makes it a natural fit.
  • Genome analysis: searching for a short motif in a chromosome billions of bases long is exactly the string-search problem. Rolling hashes appear inside BLAST and related tools.
  • File synchronization (rsync / git): rsync uses a rolling Adler-32 checksum — the same sliding-window principle — to find unchanged 512-byte blocks between file versions without transferring them.
  • Compression: LZ77 and its descendants find repeated substrings using sliding-window hashes; the rolling-hash insight is at the core of zlib, gzip, and Deflate.

The rolling hash is also a gateway concept: understanding it unlocks suffix arrays, locality-sensitive hashing, and the MinHash algorithm used in near-duplicate web-page detection.

Conclusion

Rabin-Karp's key insight is deceptively simple: instead of comparing strings character by character, represent each window as a number and slide that number forward in one arithmetic step. The result is an algorithm that runs in O(n+m)O(n + m) time on average, handles dozens of patterns as easily as one, and fits in a few lines of code.

Its worst case is still O(nm)O(nm), but randomness makes that gap vanishingly thin in practice. For the general string-search problem the algorithm is effectively solved — the rolling-hash technique is proven correct, the average bound is tight, and it has been running in production systems for nearly four decades.

The next time you use grep−Fgrep -F to search for a fixed string, or commit a file and watch git delta-compress it instantly, you are riding the same idea Rabin and Karp set in motion in 1987.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rabin-karp/Content licensed under CC BY-NC 4.0.