---
title: "String Matching: KMP & the Z-Function"
module: Sequences & Strings
moduleNumber: 5
lessonNumber: 6
order: 506
summary: |
  Two linear-time matchers that beat Rabin–Karp's expected bound with a
  worst-case guarantee and no randomness. KMP precomputes a **failure function**
  $\pi$ so a mismatch slides the pattern by $q-\pi[q-1]$ and the text pointer
  never backs up, for $O(n+m)$. The **Z-function** computes the longest
  prefix-match at every position via the Z-box, giving the same bound from a
  different angle; the two encodings of a string's self-overlap convert freely.
topics: [Strings]
sources:
  - book: CLRS
    ref: "Ch. 32 — String Matching"
  - book: Skiena
    ref: "§ — String Algorithms"
  - book: Erickson
    ref: "Ch. — String Matching"
practice:
  - title: 'Longest Happy Prefix'
    slug: longest-happy-prefix
    difficulty: Hard
  - title: 'Shortest Palindrome'
    slug: shortest-palindrome
    difficulty: Hard
  - title: 'Find the Index of the First Occurrence in a String'
    slug: find-the-index-of-the-first-occurrence-in-a-string
    difficulty: Easy
---

This builds on [String Matching: Naive & Rabin–Karp](/algorithms/sequences/string-matching).
There, Rabin–Karp removed the _per-alignment cost_ — a length-$m$ comparison
became a length-$1$ hash update — but its guarantee was only expected-time, and
it still slid the window one position at a time with no memory of what a partial
match had revealed. The two algorithms here attack the _re-reading_ instead. Both
precompute the pattern's internal self-overlap, so that after a mismatch the scan
resumes exactly where the pattern's structure permits, never re-examining a text
character it already knows. The payoff is a **worst-case** $O(n+m)$ bound with no
randomness at all.

## Knuth–Morris–Pratt: never re-read the text

KMP attacks the redundancy directly. Suppose we are matching $P$ against $T$ and
have just matched $q$ characters, $P[0 \mathinner{\ldotp\ldotp} q-1] = T[s \mathinner{\ldotp\ldotp} s+q-1]$, when $P[q]$
mismatches $T[s+q]$. The naive scan would slide $P$ by one and recompare from the
start. But the matched text $T[s \mathinner{\ldotp\ldotp} s+q-1]$ equals $P[0 \mathinner{\ldotp\ldotp} q-1]$, which we know
completely — so we can compute, _in advance and from the pattern alone_, how far
to slide so the next comparison resumes correctly without ever moving the text
pointer backward.

The information we need is the **prefix function** (or **failure function**):

> **Definition.** For each $i$, let $\pi[i]$ be the length of the longest _proper_
> prefix of $P[0 \mathinner{\ldotp\ldotp} i]$ that is also a suffix of $P[0 \mathinner{\ldotp\ldotp} i]$. ("Proper" means
> shorter than $P[0 \mathinner{\ldotp\ldotp} i]$ itself.)

For $P = \texttt{ABABAC}$ we have $\pi = [0,0,1,2,3,0]$: after matching the prefix
`ABABA` (length $5$, index $4$), its longest border is `ABA` of length $3$. So on a
mismatch having matched $q = 5$ characters, instead of restarting we keep the
already-matched border `ABA` and resume comparing at $P[\pi[q-1]] = P[3]$. The
pattern effectively slides right by $q - \pi[q-1] = 5 - 3 = 2$ positions, and the
text pointer does not move.

$$
% caption: A KMP shift. After matching ABABA, P fails on `C` vs the text (highlighted).
%          The longest border ABA realigns, sliding P right by $q-\pi[q-1]=2$ with no
%          rescanning of the text.
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  acccell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=acc, very thick, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  % text row (cell 5 highlighted: light fill + thick accent border, label drawn once)
  \foreach \c [count=\i from 0] in {A,B,A,B,A} {
    \node[cell] (t\i) at (\i*7mm, 0) {$\c$};
  }
  \node[acccell] at (5*7mm, 0) {$X$};
  \node[cell] at (6*7mm, 0) {...};
  \node[left=3mm of t0, font=\footnotesize] {$T$};
  % first copy of P, aligned at shift s
  \foreach \c [count=\i from 0] in {A,B,A,B,A} {
    \node[cell] (p\i) at (\i*7mm, -10mm) {$\c$};
  }
  \node[acccell] (pc) at (5*7mm, -10mm) {$C$};
  \node[left=3mm of p0, font=\footnotesize] {$P$};
  \draw[->, red!75!black, thick] (5*7mm, -6mm) -- (5*7mm, -9mm);
  \node[right, font=\footnotesize, text=red!75!black] at (5.6*7mm, -5mm) {mismatc\/h};
  % shifted copy of P, slid right by q - pi = 2
  \foreach \c [count=\i from 0] in {A,B,A,B,A,C} {
    \node[cell, fill=acc!8] (q\i) at ({(\i+2)*7mm}, -22mm) {$\c$};
  }
  \node[left=3mm of q0, font=\footnotesize] {P'};
  % brace-ish note
  \node[font=\footnotesize] at (10.5*7mm, -16mm) {slide by q - pi[q-1] = 2};
\end{tikzpicture}
$$

Computing $\pi$ uses the very same self-matching idea, run on $P$ against itself.
Maintain the length $k$ of the current longest border; to extend to index $i$,
follow failure links downward until $P[k] = P[i]$ or $k$ falls to $0$.

```algorithm
caption: $\textsc{Prefix-Function}(P)$ — compute the failure array $\pi$ in $O(m)$
$\pi[0] \gets 0;\ k \gets 0$
for $i \gets 1$ to $m - 1$ do
  while $k > 0$ and $P[k] \ne P[i]$ do
    $k \gets \pi[k - 1]$            // fall back
  if $P[k] = P[i]$ then
    $k \gets k + 1$                 // extend border
  $\pi[i] \gets k$
return $\pi$
```

```algorithm
caption: $\textsc{KMP-Match}(T, P)$ — scan once, never moving the text pointer back
$\pi \gets \textsc{Prefix-Function}(P)$
$q \gets 0$                          // chars matched so far
for $i \gets 0$ to $n - 1$ do
  while $q > 0$ and $P[q] \ne T[i]$ do
    $q \gets \pi[q - 1]$             // mismatch: fall back
  if $P[q] = T[i]$ then
    $q \gets q + 1$
  if $q = m$ then
    report occurrence at shift $i - m + 1$
    $q \gets \pi[q - 1]$             // allow overlapping matches
```

> **Lemma (running time).** Both procedures run in linear time, so KMP matches in
> $O(n + m)$ worst case.
>

> **Proof (amortised).** Consider the scan. The text pointer $i$ advances exactly
> $n$ times and never retreats. The matched-length variable $q$ increases by at
> most $1$ per iteration, so it increases at most $n$ times total. Every iteration
> of the inner `while` strictly _decreases_ $q$ (since $\pi[q-1] < q$), and $q$
> can never go below $0$; therefore the total number of inner-loop decrements over
> the whole run is at most the total number of increments, $\le n$. The scan thus
> does $O(n)$ work. The identical argument with $i$ ranging over $P$ bounds
> $\textsc{Prefix-Function}$ by $O(m)$. $\qed$

The key is that $q$ is a "potential" that pays for the fallback: each unit of slide
was funded by an earlier successful character match.[^clrs-kmp] No text character
is ever examined more than a constant number of times, the central property that
the naive scan lacks.

::impl{algo="kmp"}

### Building the failure function by hand

Run $\textsc{Prefix-Function}$ on $P = \texttt{ABABACA}$ and watch $k$, the
length of the current longest border. Each step tries to extend the border of
the previous prefix by one character; when that fails, $k$ falls back through
shorter borders until one extends or none is left.

- **$i = 1$:** $k = 0$; compare $P[0] = \texttt{A}$ with $P[1] = \texttt{B}$ —
  no match, and $k$ is already $0$, so $\pi[1] = 0$.
- **$i = 2$:** compare $P[0] = \texttt{A}$ with $P[2] = \texttt{A}$ — match, so
  $k = 1$ and $\pi[2] = 1$ (border `A`).
- **$i = 3$:** compare $P[1] = \texttt{B}$ with $P[3] = \texttt{B}$ — match,
  $k = 2$, $\pi[3] = 2$ (border `AB`).
- **$i = 4$:** compare $P[2] = \texttt{A}$ with $P[4] = \texttt{A}$ — match,
  $k = 3$, $\pi[4] = 3$ (border `ABA`).
- **$i = 5$:** compare $P[3] = \texttt{B}$ with $P[5] = \texttt{C}$ — mismatch.
  Fall back: $k \gets \pi[2] = 1$; compare $P[1] = \texttt{B}$ with `C` —
  mismatch again. Fall back: $k \gets \pi[0] = 0$; compare $P[0] = \texttt{A}$
  with `C` — still no. $k = 0$, so $\pi[5] = 0$. Two fallbacks, one failed
  extension: the cost of this step equals the border length that steps
  $2$–$4$ built up.
- **$i = 6$:** compare $P[0] = \texttt{A}$ with $P[6] = \texttt{A}$ — match,
  $k = 1$, $\pi[6] = 1$.

The full table, read left to right: $\pi[i]$ is the length of the longest
border of the prefix ending at column $i$.

$$
% caption: The prefix function $\pi$ for $P=\texttt{ABABACA}$. Top row: the pattern.
%          Bottom row: $\pi[i]$, the length of the longest proper prefix of
%          $P[0\mathinner{\ldotp\ldotp} i]$ that is also a suffix. E.g. $\pi[4]=3$ because
%          `ABABA` has border `ABA`.
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=8mm, inner sep=0, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c [count=\i from 0] in {A,B,A,B,A,C,A} {
    \node[cell] (c\i) at (\i*8mm, 0) {$\c$};
  }
  \fill[acc!15] (4*8mm-4mm,-8mm-4mm) rectangle (4*8mm+4mm,-8mm+4mm);
  \foreach \v [count=\i from 0] in {0,0,1,2,3,0,1} {
    \node[cell] (v\i) at (\i*8mm, -8mm) {$\v$};
  }
  \node[left=3mm of c0, font=\footnotesize] {$P[i]$};
  \node[left=3mm of v0, font=\footnotesize] {pi[i]};
  \node[cell, draw=acc, very thick] at (4*8mm, -8mm) {};
\end{tikzpicture}
$$

Step $i = 5$ shows the fallback chain in action, and the
geometry is worth drawing. Having matched the border `ABA` and failed to extend
it with `B` against `C`, the next candidate is not "border of length $2$" —
it is $\pi[2] = 1$, the longest border _of the border_. The figure shows all
three candidates being tried against column $5$ in decreasing order:

$$
% caption: Computing $\pi[5]$ for $P=\texttt{ABABACA}$: the fallback chain. Each row
%          aligns a candidate border (blue cells) under the end of the prefix and tests
%          its next character (red) against $P[5]=\texttt{C}$. Candidates are
%          $k=3$, then $\pi[2]=1$, then $\pi[0]=0$; all fail, so $\pi[5]=0$
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  bcell/.style={draw, minimum size=7mm, inner sep=0, font=\small, fill=acc!15},
  xcell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=red!75!black, very thick, fill=red!18}]
  \definecolor{acc}{HTML}{2348F2}
  % the prefix P[0..5], C highlighted
  \foreach \c [count=\i from 0] in {A,B,A,B,A} {
    \node[cell] (t\i) at (\i*7mm, 0) {$\c$};
  }
  \node[cell, draw=acc, very thick, fill=acc!15] at (5*7mm, 0) {$C$};
  \node[left=3mm of t0, font=\footnotesize] {$P[0..5]$};
  % candidate k = 3: border ABA under cols 2..4, test P[3]=B under col 5
  \node[bcell] at (2*7mm,-10mm) {$A$};
  \node[bcell] at (3*7mm,-10mm) {$B$};
  \node[bcell] at (4*7mm,-10mm) {$A$};
  \node[xcell] at (5*7mm,-10mm) {$B$};
  \node[right=4mm, font=\footnotesize, anchor=west] at (5.5*7mm,-10mm) {k = 3: P[3] = B vs C, fail};
  % candidate k = pi[2] = 1: border A under col 4, test P[1]=B under col 5
  \node[bcell] at (4*7mm,-19mm) {$A$};
  \node[xcell] at (5*7mm,-19mm) {$B$};
  \node[right=4mm, font=\footnotesize, anchor=west] at (5.5*7mm,-19mm) {k = pi[2] = 1: P[1] = B vs C, fail};
  % candidate k = 0: test P[0]=A under col 5
  \node[xcell] at (5*7mm,-28mm) {$A$};
  \node[right=4mm, font=\footnotesize, anchor=west] at (5.5*7mm,-28mm) {k = pi[0] = 0: P[0] = A vs C, fail};
  \node[font=\footnotesize] at (2.5*7mm,-36mm) {no candidate extends: pi[5] = 0};
\end{tikzpicture}
$$

Why is $\pi[k-1]$ the right place to fall back to — why not some length in
between? Because borders nest.

> **Lemma (fallback chain).** Fix $i \ge 1$ and let $k = \pi[i-1]$. The lengths
> $j$ such that $P[0 \mathinner{\ldotp\ldotp} j-1]$ is a border of $P[0 \mathinner{\ldotp\ldotp} i-1]$ — the candidates
> that could extend to a border of $P[0 \mathinner{\ldotp\ldotp} i]$ by matching $P[j] = P[i]$ — are
> exactly the chain $k > \pi[k-1] > \pi[\pi[k-1]-1] > \cdots > 0$.

> **Proof.** First, any two borders of the same string nest: if $u$ and $v$ are
> both borders with $|u| < |v|$, then $u$ is a prefix of $v$ (both are prefixes
> of the string) and a suffix of $v$ (both are suffixes), so $u$ is a border of
> $v$. Hence the borders of $P[0 \mathinner{\ldotp\ldotp} i-1]$ are: its longest border, of length
> $k$, together with all borders of that border — which by induction is
> exactly the stated chain. Second, every nonempty border of $P[0 \mathinner{\ldotp\ldotp} i]$, say
> of length $j+1$, is a border of $P[0 \mathinner{\ldotp\ldotp} i-1]$ of length $j$ extended by the
> matching character $P[j] = P[i]$: strip the last character of both copies.
> So the `while` loop enumerates _all_ candidates in decreasing order, and
> stopping at the first that extends yields the longest border of
> $P[0 \mathinner{\ldotp\ldotp} i]$ — which is the definition of $\pi[i]$. $\qed$

The construction's linearity is the same two-line count as the matcher's.
Across the whole run, $k$ increases only in the `if` (at most once per $i$, so
at most $m - 1$ times) and strictly decreases with every `while` iteration
(since $\pi[k-1] \le k - 1$). It starts at $0$ and never goes negative, so

$$
\#\text{fallbacks} \;\le\; \#\text{increments} \;\le\; m - 1,
$$

and the total work is at most $2(m-1) + O(m) = O(m)$. Step $i = 5$ above spent
two fallbacks in one step precisely because steps $2$–$4$ had deposited three
increments; the budget balances globally even though a single step can be
expensive.

### The matcher on a real text

Match $P = \texttt{ABABACA}$ against $T = \texttt{ABABABACABA}$ ($n = 11$),
carrying $\pi = [0,0,1,2,3,0,1]$ from above. The variable $q$ counts matched
characters:

- **$i = 0$–$4$:** `A`, `B`, `A`, `B`, `A` all match, $q$ climbs $1, 2, 3, 4, 5$.
- **$i = 5$:** $P[5] = \texttt{C}$ vs $T[5] = \texttt{B}$ — mismatch. Fall back
  $q \gets \pi[4] = 3$: the border `ABA` of the matched `ABABA` is still a live
  partial match, ending where we stand. Now $P[3] = \texttt{B}$ matches
  $T[5]$, so $q = 4$. The text pointer never moved; $T[3 \mathinner{\ldotp\ldotp} 4]$ was never
  re-read.
- **$i = 6$:** $P[4] = \texttt{A}$ matches, $q = 5$.
- **$i = 7$:** $P[5] = \texttt{C}$ matches, $q = 6$.
- **$i = 8$:** $P[6] = \texttt{A}$ matches, $q = 7 = m$ — report an occurrence
  at shift $i - m + 1 = 2$ (indeed $T[2 \mathinner{\ldotp\ldotp} 8] = \texttt{ABABACA}$), then reset
  $q \gets \pi[6] = 1$ so an overlapping occurrence starting with the final
  `A` stays catchable.
- **$i = 9$, $10$:** $P[1] = \texttt{B}$ and $P[2] = \texttt{A}$ match, $q$
  reaches $3$ as the text runs out.

Eleven text characters, one fallback, one report. Only $T[5]$ was compared
against the pattern twice — once failing against `C`, once matching `B` — and
no position was touched a third time, comfortably within the $2n$ comparison
budget the potential argument promises.

$$
% caption: KMP scanning $T=\texttt{ABABABACABA}$ for $P=\texttt{ABABACA}$. Below each
%          text position: the matched count $q$ after that step. At $i{=}5$ (red) the
%          mismatch drops $q$ from $5$ to $\pi[4]=3$ and re-matches to $4$; at $i{=}8$
%          (blue) $q$ reaches $m{=}7$, reporting the occurrence at shift $2$
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  rcell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=red!75!black, very thick, fill=red!18},
  acell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=acc, very thick, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i in {0,...,10} {
    \node[font=\scriptsize] at (\i*7mm, 5.5mm) {\i};
  }
  \foreach \i/\c in {0/A,1/B,2/A,3/B,4/A,6/A,7/C,9/B,10/A} {
    \node[cell] (t\i) at (\i*7mm, 0) {$\c$};
  }
  \node[rcell] at (5*7mm, 0) {$B$};
  \node[acell] at (8*7mm, 0) {$A$};
  \node[left=3mm of t0, font=\footnotesize] {$T$};
  \foreach \v [count=\i from 0] in {1,2,3,4,5,4,5,6,7,2,3} {
    \node[cell] (v\i) at (\i*7mm, -10mm) {$\v$};
  }
  \node[left=3mm of v0, font=\footnotesize] {$q$};
  \node[font=\footnotesize, red!75!black, align=left] at (12mm,-21mm)
    {i = 5: q falls 5 to 3,\\B matches: q = 4};
  \draw[->, red!75!black, thick] (26mm,-19mm) -- (34mm,-14.5mm);
  \node[font=\footnotesize, acc, align=left] at (58mm,-21mm)
    {i = 8: q = m, report shift 2,\\reset q to pi[6] = 1};
  \draw[->, acc, thick] (56mm,-17.5mm) -- (56mm,-14.5mm);
\end{tikzpicture}
$$

## The Z-function: longest prefix-match at every position

The Z-function repackages the same self-similarity into a single array, and is
often easier to implement bug-free.

> **Definition.** For a string $S$ of length $\ell$, $Z[i]$ is the length of the
> longest substring starting at position $i$ that matches a prefix of $S$; that
> is, the largest $k$ with $S[0 \mathinner{\ldotp\ldotp} k-1] = S[i \mathinner{\ldotp\ldotp} i+k-1]$. By convention $Z[0]$ is
> left undefined (or set to $\ell$).

The linear-time computation keeps a half-open window $[l, r)$, the **Z-box**:
the rightmost interval known to equal a prefix of $S$ (so $S[l \mathinner{\ldotp\ldotp} r-1] = S[0 \mathinner{\ldotp\ldotp} r-l-1]$).
For a new index $i$:

- if $i < r$, position $i$ lies inside a known prefix-match, so its mirror
  $i - l$ gives a free lower bound $Z[i] \gets \min(Z[i-l],\ r - i)$;
- then extend the match character-by-character past $r$ if possible, and if the
  match runs beyond $r$, slide the Z-box to the new $[i, i + Z[i])$.

$$
% caption: Z-box copy on $S=\texttt{ababab}$ at $i{=}4$. The box $[l,r){=}[2,6)$ already
%          matches a prefix, so the mirror $i-l{=}2$ gives a free bound
%          $Z[4]\gets\min(r{-}i,\,Z[2])=\min(2,4)=2$; here $r$ caps the copy
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \i/\c in {0/a,1/b,2/a,3/b,4/a,5/b} {
    \node[draw, minimum size=8mm, inner sep=1pt] (s\i) at (\i*0.95,0) {$\c$};
    \node[font=\footnotesize] at (\i*0.95,0.72) {\i};
  }
  \draw[acc, very thick] (1.45,-0.5) rectangle (5.25,0.48);
  \node[font=\footnotesize, acc] at (3.35,-0.95) {Z-b\/ox [l, r) = [2, 6)};
  \node[font=\footnotesize, acc] at (1.9,1.12) {mirror i - l = 2};
  \node[font=\footnotesize, acc] at (3.8,1.12) {i = 4};
  \draw[->, red!75!black, thick] (3.8,1.62) .. controls (3.2,2.1) and (2.5,2.1) .. (1.9,1.62)
    node[midway, above, font=\footnotesize, text=red!75!black, yshift=2pt]{copy};
  \node[font=\footnotesize, acc] at (3.35,-1.5) {Z[4] = min(2, Z[2] = 4) = 2};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Z-Function}(S)$ — longest prefix-match at each position in $O(\ell)$
$Z[0] \gets \ell;\ l \gets 0;\ r \gets 0$
for $i \gets 1$ to $\ell - 1$ do
  if $i < r$ then
    $Z[i] \gets \min(r - i,\ Z[i - l])$   // copy from mirror
  while $i + Z[i] < \ell$ and $S[Z[i]] = S[i + Z[i]]$ do
    $Z[i] \gets Z[i] + 1$                 // extend past the box
  if $i + Z[i] > r$ then
    $l \gets i;\ r \gets i + Z[i]$        // advance Z-box
return $Z$
```

The case split hides the whole efficiency argument, so make it explicit. When
$i < r$, the box guarantees $S[i \mathinner{\ldotp\ldotp} r-1] = S[i-l \mathinner{\ldotp\ldotp} r-l-1]$: everything from
$i$ to the box's edge is a verbatim copy of the string starting at the mirror
position $i - l$. Two things can happen:

- **Mirror case, $Z[i-l] < r - i$.** The mirror's prefix-match ended _strictly
  inside_ the copied region, mismatch included: $S[i-l+Z[i-l]] \ne S[Z[i-l]]$,
  and the corresponding character $S[i + Z[i-l]]$ is still inside the box, so
  it equals the mirror's and mismatches too. Hence $Z[i] = Z[i-l]$ exactly; the
  `while` test fails on its first probe and the box does not move. Cost: $O(1)$.
- **Extension case, $Z[i-l] \ge r - i$.** The mirror matched at least to the
  box's edge, so all of $S[i \mathinner{\ldotp\ldotp} r-1]$ matches the prefix for free — but the
  box says nothing about $S[r]$ onward. Start comparing at position $r$; every
  match pushes past everything the box ever certified, and afterward the box
  advances to $[i,\ i + Z[i])$.

(When $i \ge r$ the box is useless and we are in the extension case with a free
match of length $0$.)

> **Lemma (Z linear time).** $\textsc{Z-Function}$ makes at most $2\ell$
> character comparisons, so it runs in $O(\ell)$.

> **Proof.** Comparisons happen only in the `while` test; call a comparison a
> _hit_ if the characters match (and $Z[i]$ grows) and a _miss_ otherwise (the
> loop exits, so there is at most one miss per index $i$ — at most $\ell - 1$
> misses total). Every hit at index $i$ probes position $p = i + Z[i] \ge r$:
> in the mirror case the single probe misses, and in the extension case the
> probing starts at $r$ or beyond. After the loop, the box update sets
> $r = i + Z[i] > p$ for the last hit position $p$, and $r$ never decreases.
> So each of the $\ell$ string positions is probed by at most one hit ever:
> at most $\ell$ hits. Total comparisons $\le 2\ell$. $\qed$

### A full trace

Run it on $S = \texttt{aabcaabxaaaz}$ ($\ell = 12$), chosen so both cases fire:

- **$i = 1$:** box empty; compare fresh: $S[0] = \texttt{a} = S[1]$, then
  $S[1] = \texttt{a} \ne S[2] = \texttt{b}$. $Z[1] = 1$, box $[1, 2)$.
- **$i = 2$, $3$:** fresh compares fail at once ($\texttt{b} \ne \texttt{a}$,
  $\texttt{c} \ne \texttt{a}$): $Z[2] = Z[3] = 0$.
- **$i = 4$:** fresh: `aab` matches, then $S[3] = \texttt{c} \ne S[7] = \texttt{x}$.
  $Z[4] = 3$, box $[4, 7)$.
- **$i = 5$:** inside the box; mirror $i - l = 1$ has $Z[1] = 1 < r - i = 2$.
  **Mirror case:** $Z[5] = 1$, one failed probe, box unchanged. (Indeed
  $S[5] = \texttt{a}$, $S[6] = \texttt{b} \ne S[1] = \texttt{a}$ — the mirror's
  mismatch, replayed.)
- **$i = 6$:** mirror $Z[2] = 0 < r - i = 1$: mirror case again, $Z[6] = 0$.
- **$i = 7$:** $i = r$, so outside the box: fresh compare, $\texttt{x} \ne
  \texttt{a}$, $Z[7] = 0$.
- **$i = 8$:** fresh: `aa` matches, $S[2] = \texttt{b} \ne S[10] = \texttt{a}$.
  $Z[8] = 2$, box $[8, 10)$.
- **$i = 9$:** inside the box; mirror $Z[1] = 1 \ge r - i = 1$. **Extension
  case:** the first character is free, and comparing at $r = 10$ gives
  $S[1] = \texttt{a} = S[10]$ — a hit past the old box — then
  $S[2] = \texttt{b} \ne S[11] = \texttt{z}$. $Z[9] = 2$, box advances to
  $[9, 11)$.
- **$i = 10$:** mirror $Z[1] = 1 \ge r - i = 1$: extension case; the probe at
  $r = 11$ fails ($\texttt{z} \ne \texttt{a}$... precisely $S[1] = \texttt{a}
  \ne S[11] = \texttt{z}$), so $Z[10] = 1$ and the box stays.
- **$i = 11$:** outside the box ($i = r$): fresh compare fails, $Z[11] = 0$.

The result is $Z = [12, 1, 0, 0, 3, 1, 0, 0, 2, 2, 1, 0]$, computed with eight
hits and ten misses — inside the $2\ell = 24$ budget with room to spare.

$$
% caption: The two Z-box cases on $S=\texttt{aabcaabxaaaz}$. Top ($i{=}5$, box $[4,7)$):
%          the mirror's match ends inside the box, so $Z[5]=Z[1]=1$ is copied and no
%          probe succeeds. Bottom ($i{=}9$, box $[8,10)$): the mirror reaches the box
%          edge, so comparison resumes at $r{=}10$; the `a` matches (blue), the `z`
%          fails (red), $Z[9]=2$ and the box advances to $[9,11)$
\begin{tikzpicture}[
  >=stealth, font=\small,
  cell/.style={draw, minimum size=7mm, inner sep=0, font=\small},
  hitcell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=acc, very thick, fill=acc!15},
  misscell/.style={draw, minimum size=7mm, inner sep=0, font=\small, draw=red!75!black, very thick, fill=red!18}]
  \definecolor{acc}{HTML}{2348F2}
  % ---- panel 1: i = 5, mirror case ----
  \foreach \i in {0,...,11} {
    \node[font=\scriptsize] at (\i*7mm, 5.5mm) {\i};
  }
  \foreach \c [count=\i from 0] in {a,a,b,c,a,a,b,x,a,a,a,z} {
    \node[cell] at (\i*7mm, 0) {$\c$};
  }
  \draw[acc, very thick] (24.8mm,-4.2mm) rectangle (45.2mm,4.2mm);
  \draw[->, red!75!black, thick] (35mm,9.5mm) .. controls (28mm,13.5mm) and (14mm,13.5mm) .. (7mm,9.5mm)
    node[midway, above, font=\footnotesize, text=red!75!black, yshift=2pt]{copy from mirror};
  \node[font=\footnotesize, acc] at (35mm,-8mm) {Z-b\/ox [4, 7)};
  \node[font=\footnotesize] at (38mm,-14mm) {case 1 at i = 5: Z[1] = 1 $<$ r - i = 2, so Z[5] = 1, done};
  % ---- panel 2: i = 9, extension case ----
  \begin{scope}[yshift=-34mm]
    \foreach \c [count=\i from 0] in {a,a,b,c,a,a,b,x,a,a} {
      \node[cell] at (\i*7mm, 0) {$\c$};
    }
    \node[hitcell] at (10*7mm, 0) {$a$};
    \node[misscell] at (11*7mm, 0) {$z$};
    \draw[acc, very thick] (52.8mm,-4.2mm) rectangle (66.2mm,4.2mm);
    \node[font=\footnotesize, acc] at (48mm,-8mm) {Z-b\/ox [8, 10)};
    \node[font=\footnotesize] at (70mm,-8mm) {probes at 10, 11};
    \node[font=\footnotesize] at (38mm,-14mm) {case 2 at i = 9: Z[1] = 1 = r - i, so compare past r: Z[9] = 2};
  \end{scope}
\end{tikzpicture}
$$

To match $P$ in $T$, run the Z-function on the concatenation $S = P \,\#\, T$,
where `#` is a sentinel in neither $P$ nor $T$. Wherever $Z[i] \ge m$ inside the
$T$ portion, the prefix $P$ matches in full at that spot, so $P$ occurs in $T$ at
shift $i - (m + 1)$. The sentinel prevents a match from straddling the boundary
and caps $Z[i] \le m$. Total length is $n + m + 1$, so matching is $O(n + m)$.

> **Intuition.** KMP's $\pi$ and the Z-function carry the same information from two
> directions ($\pi$ measures borders _ending_ at each position, $Z$ measures
> prefix-matches _starting_ at each position) and either can be converted to the
> other in linear time. Use whichever is easier to write correctly;
> Z-arrays tend to win on problems about prefixes, periods, and palindromes.[^erickson-z]

::impl{algo="z_function"}

## What the tables give you for free

The self-overlap tables answer far more than "does $P$ occur in $T$". Two payoffs
recur so often they are worth naming.

**Periods and repetitions.** A string $S$ of length $\ell$ has **period** $p$ if
$S[i] = S[i+p]$ wherever both are defined — equivalently, $S[0 \mathinner{\ldotp\ldotp} \ell-p-1]$ is
a border of $S$. So the smallest period is $\ell - \pi[\ell-1]$, read straight off
the last prefix-function entry. For $P = \texttt{ABABABA}$ ($\ell = 7$), the
longest border has length $5$ (`ABABA`), so the smallest period is $7 - 5 = 2$:
the string is `AB` repeated, plus a trailing `A`. From the Z-side, $S$ is a full
$k$-fold repetition of a block of length $p$ exactly when $Z[p] = \ell - p$ and
$p \mid \ell$. This is the whole content of **Longest Happy Prefix** (report the
longest border, $\pi[\ell-1]$) and of "is this string a repeated block?".

**Prefix structure and palindromes.** Because $Z[i]$ is the longest prefix-match
starting at $i$, a single Z-pass over a cleverly chosen concatenation solves a
family of problems: prepend the reverse of $S$ with a sentinel to test which
prefixes of $S$ are palindromes (the idea behind **Shortest Palindrome**), or run
Z on $P\#T$ to find every occurrence with match _lengths_ attached, which the
plain boolean matcher discards.

$$
% caption: Reading the smallest period off $\pi$. For $S=\texttt{ABABABA}$ the longest
%          border is `ABABA` (length 5), so period $=\ell-\pi[\ell{-}1]=7-5=2$: the block
%          `AB' tiles $S$ with one character left over
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum size=7.5mm, inner sep=0, font=\small},
  bcell/.style={draw, minimum size=7.5mm, inner sep=0, font=\small, fill=acc!15}]
  \definecolor{acc}{HTML}{2348F2}
  \foreach \c [count=\i from 0] in {A,B,A,B,A,B,A} {
    \node[cell] (c\i) at (\i*7.5mm, 0) {$\c$};
  }
  \node[left=3mm of c0, font=\footnotesize] {$S$};
  % underline the border prefix and suffix
  \draw[acc, very thick] (-3.75mm,-4.5mm) -- (33.75mm,-4.5mm);
  \node[font=\footnotesize, acc] at (15mm,-8mm) {border ABABA (pi[6] = 5)};
  \draw[acc, very thick] (18.75mm,4.5mm) -- (56.25mm,4.5mm);
  \node[font=\footnotesize, acc] at (37.5mm,8mm) {same as a tail};
  \node[font=\footnotesize] at (26mm,-14mm) {period = 7 - 5 = 2, block AB};
\end{tikzpicture}
$$

## Choosing a matcher

Across both string-matching lessons there are four correct algorithms; the choice
is about constants, guarantees, and what else the problem asks for.

- **Naive** wins more often than its worst case suggests. For $m \le 4$ or so,
  or for a one-off search in text without heavy repetition, the expected cost
  is $O(n)$ with tiny constants and zero preprocessing. Reject it only when the
  input may be adversarial or repetitive.
- **Rabin–Karp** is the only one that generalizes cheaply to **many patterns at
  once** and to numeric or 2-D fingerprinting; its guarantee is expected-time
  only, and soundness depends on the verify step.
- **KMP** gives the worst-case $O(n + m)$ bound with no randomness, and its
  scan is **online**: it reads $T$ strictly left to right, one character at a
  time, keeping only $q$ and the $\pi$ table between characters. That makes it
  suitable for streams too large to store and the conceptual basis for
  matching automata ([Aho–Corasick](/algorithms/sequences/suffix-arrays-and-aho-corasick)
  is KMP's failure idea on a trie of many patterns).
- **Z** matches KMP's guarantee when the whole input can be concatenated up
  front, and the array it produces is often the main value: periods, borders,
  and prefix structure read straight off it. Many string exercises reduce to
  one Z-pass plus a scan.

To summarize both lessons: naive re-derives information it already had;
hashing compresses a window to a comparable summary; $\pi$ and $Z$ precompute the
pattern's self-overlap so no information is ever re-derived. The next lesson
pushes the same idea further, preprocessing the _text_ itself into
[suffix arrays](/algorithms/sequences/suffix-arrays-and-aho-corasick) so that
many queries against one text each cost near nothing.

## The string-matching lineage and periodicity theory

KMP is named for the 1977 paper of Knuth, Morris, and Pratt (_Fast Pattern
Matching in Strings_, SIAM J. Comput.), the result that first broke the $O(nm)$
barrier for exact matching in the worst case; Morris and Pratt had the linear
matcher and Knuth supplied the analysis connecting it to the theory of periods.
The **Boyer–Moore** algorithm (Boyer & Moore, _A Fast String Searching
Algorithm_, CACM 1977), published the same year, attacks the problem from the
opposite end — it matches the pattern _right to left_ and uses a "bad character"
rule to skip ahead by more than one position, so on typical text it examines
_sublinear_ in $n$ characters and is what `grep` and many `memmem`
implementations actually use.

The prefix-function / period machinery is also the gateway to the deeper theory
of **string periodicity**. The Fine–Wilf theorem (Fine & Wilf, 1965) states that
if a string of length $\ell$ has two periods $p$ and $q$ with $p + q \le \ell +
\gcd(p,q)$, then it also has period $\gcd(p, q)$ — the structural fact behind
the nesting of border chains, and the reason KMP's fallback is well-defined. The same
periodicity theory drives modern results such as constant-space and packed
string matching, and the failure-link idea generalizes directly to the
[Aho–Corasick automaton](/algorithms/sequences/suffix-arrays-and-aho-corasick)
for many patterns and to suffix automata for indexing a text.

The Z-function, by contrast, is folklore rather than a single named paper — it is
the "$Z$-algorithm" of the competitive-programming and stringology literature
(Gusfield's _Algorithms on Strings, Trees, and Sequences_, 1997, presents it as
the fundamental preprocessing tool and derives KMP, Boyer–Moore, and more from
it). Its appeal is pedagogical and practical in equal measure: one short,
hard-to-get-wrong loop that exposes a string's entire prefix structure, from
which periods, borders, and many matching problems fall out by a single scan.

## Takeaways

- **KMP** precomputes the **prefix/failure function** $\pi$, so on a mismatch the
  pattern slides by $q - \pi[q-1]$ and the text pointer never backs up:
  worst-case **$O(n+m)$**, justified by an amortised potential argument on $q$.
- The failure array is built by the **same** two-pointer self-matching, in $O(m)$;
  its correctness rests on the fact that a string's **borders nest**, so the
  fallback chain enumerates every candidate in decreasing order.
- The **Z-function** computes the longest prefix-match at every position in $O(n)$
  via the **Z-box**; running it on $P\,\#\,T$ and finding $Z[i] \ge m$ matches in
  **$O(n+m)$**.
- $\pi$ and $Z$ are **interconvertible** — two encodings of a string's
  self-similarity — and both give **periods** for free: the smallest period is
  $\ell - \pi[\ell-1]$.
- KMP/Z give worst-case guarantees with no randomness; Rabin–Karp trades that for
  simplicity and multi-pattern flexibility. KMP's **online** scan handles
  unbounded streams.

[^clrs-kmp]: **CLRS**, Ch. 32 — String Matching (§32.4): the prefix function $\pi$ and the amortised $O(n+m)$ KMP analysis.
[^erickson-z]: **Erickson**, Ch. — String Matching: the Z-function / failure-function duality and the Z-box linear-time computation.