Rabin-Karp Search

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 \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)$ per step — by updating the hash algebraically rather than recomputing it from scratch.

The resulting algorithm finds any pattern in $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.

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>{{lbl_pattern}} <input id="pat" type="text" value="abc" maxlength="12" /></label>
  <label>{{lbl_text}} <input id="txt" type="text" value="xabcyabcz" maxlength="40" /></label>
</div>
<div class="hash-row">
  <span class="label">{{lbl_pattern_hash}}</span>
  <span id="phash" class="hashval">—</span>
  <span class="label" style="margin-left:1.2rem">{{lbl_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">{{btn_prev}}</button>
  <button id="btnNext" type="button">{{btn_next}}</button>
  <button id="btnAuto" type="button">{{btn_auto_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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)$ time. Compute the base-power term $b^{m-1} \bmod q$ used to drop the outgoing character.
• Sliding: each of the n−m+1 positions costs $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)$. 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)$. If every window is a false positive (e.g., text = "aaa…a", pattern = "aaa…b"), each position triggers an $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)$ and failure probability that falls off exponentially.
• Multiple patterns: hash all k patterns into a hash set; each window check is $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)$ 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.

"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.

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)$ 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)$, 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 -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.