---
title: "String Matching: Naive & Rabin–Karp"
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 5
order: 505
summary: |
  Given a text $T$ of length $n$ and a pattern $P$ of length $m$, find every
  occurrence of $P$ in $T$. The naive scan costs $O(nm)$ and re-reads text it has
  already seen. Rabin–Karp fixes the first inefficiency with a **rolling hash**:
  each length-$m$ window is summarized by one number, updated in $O(1)$ per slide,
  verified on a hash match to kill collisions, for expected $O(n+m)$. A companion
  lesson removes the re-reading entirely with KMP and the Z-function.
topics: [Strings]
sources:
  - book: CLRS
    ref: "Ch. 32 — String Matching"
  - book: Skiena
    ref: "§ — String Algorithms"
  - book: Erickson
    ref: "Ch. — String Matching"
practice:
  - title: 'Find the Index of the First Occurrence in a String'
    slug: find-the-index-of-the-first-occurrence-in-a-string
    difficulty: Easy
  - title: 'Repeated String Match'
    slug: repeated-string-match
    difficulty: Medium
  - title: 'Longest Duplicate Substring'
    slug: longest-duplicate-substring
    difficulty: Hard
---

We have spent the previous lessons treating a sequence as a bag of comparable
keys. A string is more rigid: its characters come in a fixed order and that order
_is_ the information. The fundamental question is **string matching**: given a
text $T[0 \mathinner{\ldotp\ldotp} n-1]$ and a pattern $P[0 \mathinner{\ldotp\ldotp} m-1]$ over some alphabet $\Sigma$,
report every shift $s$ such that $P$ occurs in $T$ starting at position $s$, i.e.
$T[s \mathinner{\ldotp\ldotp} s+m-1] = P$. There are $n - m + 1$ candidate shifts, and the art is to
test them without paying $m$ comparisons apiece.

Correctness of a matcher has the two standard halves of any search procedure: it
must be [sound](/algorithms/foundations/what-is-an-algorithm) — every reported
shift is a genuine occurrence — and [complete](/algorithms/foundations/what-is-an-algorithm)
— every occurrence is reported. The naive scan is trivially both (it returns a
shift only after verifying all $m$ characters, and it tries every shift); the
interest in what follows is keeping both guarantees while doing far less work.

The naive answer does pay that price, and there are two distinct redundancies to
attack. The first is the _cost per alignment_: naive spends up to $m$ comparisons
to test one shift. The second is _re-reading_: after a partial match fails, naive
slides the pattern by one and re-examines text characters it already knows.
This lesson removes the first with **Rabin–Karp**, which replaces a length-$m$
comparison by a length-$1$ hash update. The [companion lesson](/algorithms/sequences/kmp-and-z-function)
removes the second with **KMP** and the **Z-function**, which precompute the
pattern's self-overlap so no text character is ever re-derived.

## The naive scan, and why it wastes work

Try every alignment; at each, compare characters until one disagrees or the whole
pattern matches.

```algorithm
caption: $\textsc{Naive-Match}(T, P)$ — test all $n-m+1$ alignments
for $s \gets 0$ to $n - m$ do
  $j \gets 0$
  while $j < m$ and $T[s + j] = P[j]$ do
    $j \gets j + 1$
  if $j = m$ then
    report occurrence at shift $s$
```

> **Lemma (naive running time).** $\textsc{Naive-Match}$ runs in $\Theta((n-m+1)\,m)
> = O(nm)$ in the worst case, realized by $T = \texttt{aaaa...a}$ and
> $P = \texttt{aaa...ab}$, where every alignment matches $m-1$ characters before
> failing. The outer loop runs $n - m + 1$ times and the inner loop up to $m$, so
> the product is the bound, and the family above attains it.

On random or low-repetition text the inner loop almost always dies on
the first character, so naive matching averages $O(n)$ and is the right
tool when $m$ is tiny or the text is unstructured.[^clrs-naive] The pathology is
_repetitive_ patterns; the fix is to stop discarding what a partial match
revealed. The [asymptotic](/algorithms/foundations/asymptotic-analysis) gap
between the worst and average cases is what Rabin–Karp — and the KMP and
Z-function of the companion lesson — close.

::impl{algo="naive_match"}

> **Intuition.** When $P = \texttt{ABABAC}$ matches `ABABA` of the text and then
> fails on the sixth character, the naive scan slides $P$ forward by one and
> re-examines those same text characters. But we already _know_ those characters —
> they were `ABABA`. The faster algorithms exploit the pattern's internal
> structure so that this re-reading never happens.

$$
% caption: Why the naive scan is $O(nm)$: on $T=\texttt{aaaaab}$, $P=\texttt{aab}$ every
%          shift re-reads the same `a`s, matching $m{-}1$ of them before failing on the
%          final character (red). Each row is one alignment
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  fail/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=red!75!black, very thick, fill=red!18},
  ok/.style={draw, minimum size=7mm, inner sep=0, font=\small, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  % text row
  \foreach \c [count=\i from 0] in {a,a,a,a,a,b} {
    \node[cell] (t\i) at (\i*7mm, 0) {$\c$};
  }
  \node[left=3mm of t0, font=\footnotesize] {$T$};
  % shift 0: aa match, b fails
  \node[ok] at (0*7mm,-9mm) {$a$};
  \node[ok] at (1*7mm,-9mm) {$a$};
  \node[fail] at (2*7mm,-9mm) {$b$};
  \node[font=\footnotesize] at (-9mm,-9mm) {$s{=}0$};
  % shift 1
  \node[ok] at (1*7mm,-18mm) {$a$};
  \node[ok] at (2*7mm,-18mm) {$a$};
  \node[fail] at (3*7mm,-18mm) {$b$};
  \node[font=\footnotesize] at (-9mm,-18mm) {$s{=}1$};
  % shift 2
  \node[ok] at (2*7mm,-27mm) {$a$};
  \node[ok] at (3*7mm,-27mm) {$a$};
  \node[fail] at (4*7mm,-27mm) {$b$};
  \node[font=\footnotesize] at (-9mm,-27mm) {$s{=}2$};
  \node[font=\footnotesize, red!75!black, align=left] at (62mm,-18mm)
    {every shift re-reads\\the same a's};
\end{tikzpicture}
$$

## Rabin–Karp: matching by rolling hash

Rabin–Karp turns "are these $m$ characters equal?" into "are these two numbers
equal?" by [hashing](/algorithms/data-structures/hash-tables) each window.
Interpret each length-$m$ block of text as an $m$-digit number in base
$b = |\Sigma|$ (mapping characters to digits), reduced modulo a prime $q$ to keep
it machine-word-sized. Precompute the pattern's hash $p = h(P)$ and the first
window's hash $t_0 = h(T[0 \mathinner{\ldotp\ldotp} m-1])$. Slide the window one step at a time; if
$t_s = p$, the block _might_ match, so verify it character-by-character to rule out
a hash collision (a _spurious hit_).

This verification is what makes the matcher sound. The hash test alone is
_complete_ — equal blocks always hash equal, so a true occurrence never escapes the
$t_s = p$ filter — but it is **not sound on its own**: a collision ($t_s = p$ on
differing blocks) would report a phantom match. The character-by-character recheck
discharges that, so soundness lives in the verification and completeness lives in
the hash filter; reporting a hash match _without_ rechecking would be an unsound
algorithm.

The key step is the **rolling hash**: when the window slides from position $s$ to
$s+1$, we do not recompute the hash from scratch. We drop the contribution of the
departing high-order digit $T[s]$, shift the remaining digits up by one place
(multiply by $b$), and add the incoming low-order digit $T[s+m]$:

$$
h' \;=\; \parens{b\,(h - T[s]\,b^{\,m-1}) + T[s+m]} \bmod q .
$$

The factor $b^{m-1} \bmod q$ is precomputed once. Each slide is $O(1)$ arithmetic,
so building all $n - m + 1$ window hashes costs $O(n)$ in total.

$$
% caption: The rolling hash slides the length-$m$ window by one: drop the departing high
%          digit $T[s]\,b^{m-1}$, multiply the rest by $b$, add the incoming low digit
%          $T[s{+}m]$ — one $O(1)$ update giving $h'$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\c in {0/c,1/a,2/b,3/c,4/a,5/b} {
    \node[draw, minimum size=8mm, inner sep=1pt] (t\i) at (\i*0.95,0) {$\c$};
  }
  \draw[black, very thick] (-0.46,-0.5) rectangle (2.31,0.5);
  \node[font=\footnotesize] at (0.65,0.95) {window s: hash h};
  \draw[acc, very thick] (0.49,-0.63) rectangle (3.31,0.63);
  \node[font=\footnotesize, acc] at (2.9,-1.1) {window s+1: hash h'};
  \draw[->, red!75!black, thick] (-0.75,-1.15) -- (-0.1,-0.72);
  \node[font=\footnotesize, red!75!black] at (-1.0,-1.45) {drop $T[s]$};
  \draw[->, red!75!black, thick] (3.75,1.2) -- (2.95,0.72);
  \node[font=\footnotesize, red!75!black] at (4.35,1.45) {add $T[s{+}m]$};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Rabin-Karp}(T, P, b, q)$ — hash, slide, verify
$p \gets 0;\ t \gets 0;\ \rho \gets b^{\,m-1} \bmod q$
for $j \gets 0$ to $m - 1$ do          // hash $P$ and window 0
  $p \gets (b \cdot p + P[j]) \bmod q$
  $t \gets (b \cdot t + T[j]) \bmod q$
for $s \gets 0$ to $n - m$ do
  if $t = p$ then                       // verify, kill collisions
    if $T[s \mathinner{\ldotp\ldotp} s+m-1] = P$ then report occurrence at shift $s$
  if $s < n - m$ then                   // roll window forward
    $t \gets (b\,(t - T[s]\cdot\rho) + T[s+m]) \bmod q$
```

### The arithmetic, worked

Decimal strings make the "digits" literal. Take $b = 10$, prime $q = 13$,
pattern $P = \texttt{31415}$ (so $m = 5$), and text
$T = \texttt{2359023141526739921}$ (so $n = 19$).[^clrs-rk] Two precomputations:

$$
p = 31415 \bmod 13 = 7
\qquad\text{(since } 31415 = 2416 \cdot 13 + 7\text{)},
$$

$$
\rho = b^{\,m-1} \bmod q = 10^4 \bmod 13 = 3
\qquad\text{(since } 10000 = 769 \cdot 13 + 3\text{)}.
$$

The first window is $T[0 \mathinner{\ldotp\ldotp} 4] = 23590$, and $23590 = 1814 \cdot 13 + 8$, so
$t_0 = 8$. Now roll, one digit out and one digit in each time:

- **$s = 0 \to 1$** (window $23590 \to 35902$): drop the leading $2$, whose
  place value mod $q$ is $\rho = 3$; append the new low digit $T[5] = 2$.
  $$
  t_1 = \parens{10\,(8 - 2 \cdot 3) + 2} \bmod 13 = 22 \bmod 13 = 9 .
  $$
  Check directly: $35902 = 2761 \cdot 13 + 9$, as claimed.
- **$s = 1 \to 2$** (window $35902 \to 59023$): drop the $3$, append $T[6] = 3$.
  $$
  t_2 = \parens{10\,(9 - 3 \cdot 3) + 3} \bmod 13 = 3 .
  $$
- **$s = 2 \to 3$** (window $59023 \to 90231$): drop the $5$, append $T[7] = 1$.
  $$
  t_3 = \parens{10\,(3 - 5 \cdot 3) + 1} \bmod 13 = -119 \bmod 13 = 11 ,
  $$
  because $-119 + 10 \cdot 13 = 11$. The intermediate value went negative — the
  subtraction removed more than the running hash held — and the final mod folds
  it back into $[0, q)$. Implementations add a multiple of $q$ before reducing
  (or use a language whose `mod` is already non-negative); forgetting this is
  the classic Rabin–Karp bug.
- **$s = 3 \to 4$** (window $90231 \to 02314$): drop the $9$, append $T[8] = 4$.
  $$
  t_4 = \parens{10\,(11 - 9 \cdot 3) + 4} \bmod 13 = -156 \bmod 13 = 0 ,
  $$
  since $156 = 12 \cdot 13$ exactly.

None of $8, 9, 3, 11, 0$ equals $p = 7$, so these four shifts are dismissed with
no character comparisons at all. Continuing the scan, the window at $s = 6$ is
$T[6 \mathinner{\ldotp\ldotp} 10] = 31415$ with hash $7$: the filter fires, verification compares all
five characters, and a genuine occurrence is reported. But the window at
$s = 12$ is $T[12 \mathinner{\ldotp\ldotp} 16] = 67399$, and $67399 = 5184 \cdot 13 + 7$ — hash $7$
again. The filter fires on a block that is not the pattern, verification
compares $6 \ne 3$ and rejects, and the scan moves on. That is a **spurious
hit**: two different 5-digit numbers that happen to agree mod
$13$. A matcher that skipped verification would have reported a phantom
occurrence at shift $12$.

$$
% caption: One roll step with the numbers of the worked example ($b=10$, $q=13$,
%          $\rho = 10^4 \bmod 13 = 3$). The window slides from $23590$ ($t_0=8$) to
%          $35902$ ($t_1=9$): subtract the departing digit times $\rho$, multiply by
%          $10$, add the arriving digit, reduce mod $13$
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\c in {0/2,1/3,2/5,3/9,4/0,5/2,6/3} {
    \node[draw, minimum size=8mm, inner sep=1pt] (t\i) at (\i*0.95,0) {\c};
  }
  \node at (7*0.95,0) {...};
  \draw[black, very thick] (-0.46,-0.5) rectangle (4.21,0.5);
  \node[font=\footnotesize] at (1.0,0.95) {window 0: t = 8};
  \draw[acc, very thick] (0.49,-0.63) rectangle (5.21,0.63);
  \node[font=\footnotesize, acc] at (4.3,-1.1) {window 1: t = 9};
  \draw[->, red!75!black, thick] (-0.75,-1.15) -- (-0.1,-0.72);
  \node[font=\footnotesize, red!75!black] at (-1.1,-1.45) {drop 2, weight 3};
  \draw[->, red!75!black, thick] (5.6,1.2) -- (4.85,0.72);
  \node[font=\footnotesize, red!75!black] at (6.1,1.45) {add 2};
  \node[font=\footnotesize] at (2.4,-2.1) {\texttt{t = (10*(8 - 2*3) + 2) mod 13 = 22 mod 13 = 9}};
\end{tikzpicture}
$$

> **Lemma (running time).** Rabin–Karp runs in $O(n + m)$ _expected_ time and
> $O(nm)$ worst case.
>

> **Proof sketch.** Hashing the pattern and the first window is $O(m)$; each of the
> $n-m$ rolls is $O(1)$, so the scan itself is $O(n+m)$. The only extra cost is
> verification. A real match must be verified, and there are at most as many real
> matches as occurrences. A _spurious_ hit happens when $t_s = p$ but the blocks
> differ; for a well-chosen prime $q$ the probability of a collision at a given
> shift is about $1/q$, so the expected number of spurious verifications is
> $O(n/q)$, each costing $O(m)$. With $q$ chosen larger than $m$ this contributes
> $O(n)$ expected. Adversarially, or with an unlucky $q$, _every_ shift can
> collide, forcing a length-$m$ verification each time: $O(nm)$. $\qed$

The $1/q$ estimate can be made precise. A spurious hit at shift $s$ means $q$
divides the nonzero difference $D_s = \mathrm{val}(T[s \mathinner{\ldotp\ldotp} s+m-1]) - \mathrm{val}(P)$,
where $\mathrm{val}$ reads a block as a base-$b$ number. Since $|D_s| < b^m$,
the number $D_s$ has fewer than $m \log_2 b$ distinct prime factors (each prime
factor is at least $2$, so $k$ factors force $|D_s| \ge 2^k$). If $q$ is drawn
uniformly from the primes below some bound $M$ — and there are roughly
$M / \ln M$ of them — the chance that $q$ happens to divide $D_s$ is at most

$$
\frac{m \log_2 b}{\pi(M)} \approx \frac{m \ln M \, \log_2 b}{M},
$$

and summing over all $n - m + 1$ shifts, choosing $M \approx m n^2$ drives the
expected total number of spurious hits below $O(1/n) \cdot n = O(1)$: with
probability tending to $1$, _no_ shift collides spuriously and the whole run is
$O(n + m)$. The randomness lives in the choice of $q$, not in the input; an
adversary who sees $q$ before choosing $T$ can still manufacture collisions at
every shift, which is why a fresh random prime per run (or per process) is the
correct way to deploy the algorithm. With a _fixed_ $q$, the $1/q$ heuristic
treats the hash values as uniform — accurate for typical data, void as a
worst-case guarantee.

Rabin–Karp is most useful when matching **many** patterns of the same length at
once (hash them all, look each window up in a set) or when the "comparison" is
naturally numeric. The rolling-hash idea reappears in deduplication,
plagiarism detection, and content-defined chunking.[^skiena-rk]

::impl{algo="rabin_karp"}

## When Rabin–Karp is the right tool

Rabin–Karp's guarantee is expected-time, not worst-case, and its soundness
depends on the verify step. In exchange, it handles two settings the worst-case
matchers of the
[companion lesson](/algorithms/sequences/kmp-and-z-function) cannot handle cheaply.

- **Many patterns at once.** Hash all $k$ same-length patterns into a set; each
  window costs one $O(1)$ hash update plus one set lookup, so searching for all
  $k$ patterns together is $O(n + km)$ expected — where a per-pattern rerun of a
  single-pattern matcher would pay $O(kn)$. This is the natural tool for
  "does the text contain any of these forbidden words of length $m$?"
- **Numeric or higher-dimensional comparison.** When the "characters" are
  already numbers, or the objects are 2-D blocks, the fingerprint idea extends
  directly: a 2-D rolling hash matches an $m \times m$ pattern in an
  $n \times n$ grid, and the same fingerprint answers "find any repeated
  length-$L$ block" — the core of duplicate detection.

Reject Rabin–Karp when you need a hard worst-case bound with no randomness, or
when a single fixed $q$ could be attacked: an adversary who sees $q$ before
choosing $T$ can force a collision at every shift, degrading the run to $O(nm)$.
A fresh random prime per run avoids this.

## Fingerprints, deduplication, and anti-hash attacks

The rolling hash is one instance of a **fingerprint**: a short, cheaply updated
summary of a long object such that equal objects always share a fingerprint and
unequal ones rarely do. Karp and Rabin's original paper (Karp & Rabin,
_Efficient Randomized Pattern-Matching Algorithms_, IBM J. Res. Dev., 1987)
framed it exactly this way, and the same idea now runs far beyond substring
search. **Content-defined chunking** — used by the `rsync` protocol (Tridgell &
Mackerras, 1996) and by modern deduplicating backup and version-control systems —
slides a rolling hash across a file and cuts a new chunk boundary whenever the
hash hits a distinguished value, so that inserting a byte near the front shifts
only one chunk instead of realigning the entire file. **Rabin fingerprinting**
over polynomials (Rabin, _Fingerprinting by Random Polynomials_, 1981) is the
same construction with xor-based arithmetic, chosen for provably low collision
probability, and underlies network deduplication and similarity detection.

The polynomial hash also connects to a subtle practical failure. A single fixed
modulus $q$ is vulnerable to **anti-hash tests**: adversarial inputs built to
collide, which is why competitive-programming folklore uses a random base and a
64-bit modulus, or two independent hashes combined, to make a collision
astronomically unlikely without needing per-run randomness. The general lesson —
that a hash's worst case is only as good as the attacker's ignorance of its
parameters — is the same one that pushed hash tables toward
[universal hashing](/algorithms/data-structures/hash-tables), and it is why
security-sensitive code uses cryptographic hashes rather than the fast
polynomial ones.

## Takeaways

- **String matching** seeks all shifts where pattern $P$ ($m$ chars) occurs in
  text $T$ ($n$ chars). The **naive scan** tries all $n-m+1$ alignments in $O(nm)$
  worst case, but is fine for tiny patterns or unstructured text — and it is what
  production `strstr`/`memmem` typically use, in a hardware-tuned form.
- **Rabin–Karp** compares a **rolling hash** of each length-$m$ window, updated in
  $O(1)$ via $h' = (b(h - T[s]\,b^{m-1}) + T[s+m]) \bmod q$, then verifies on hash
  matches to kill collisions: **expected $O(n+m)$**, worst case $O(nm)$.
- A hash match that is _not_ the pattern is a **spurious hit**; the character
  recheck is what keeps the matcher **sound**, and choosing a random prime $q$
  makes spurious hits rare in expectation over the randomness of $q$, not the input.
- Rabin–Karp is the matcher of choice for **many patterns at once** and for
  numeric or 2-D fingerprinting; its guarantee is expected-time only.

This continues in [String Matching: KMP & the Z-Function](/algorithms/sequences/kmp-and-z-function),
which removes the re-reading entirely and delivers a worst-case $O(n+m)$ bound
with no randomness.

[^clrs-naive]: **CLRS**, Ch. 32 — String Matching (§32.1): the naive matcher and its $O((n-m+1)m)$ bound.
[^skiena-rk]: **Skiena**, § — String Algorithms: the Rabin–Karp rolling hash and its use for substring search and fingerprinting.
[^clrs-rk]: **CLRS**, Ch. 32 — String Matching (§32.2): the Rabin–Karp algorithm; the $31415 \bmod 13$ text is CLRS's own worked example, spurious hit included.