String Matching: KMP & the Z-Function

This builds on String Matching: Naive & Rabin–Karp. 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..q-1]=T[s..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..s+q-1]$ equals $P[0..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):

For $P=\text{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.

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

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.¹ No text character is ever examined more than a constant number of times, the central property that the naive scan lacks.

def prefix_function(pattern: str) -> list[int]:
  """
    The failure array pi, where `pi[i]` is the length of the longest proper\n
    prefix of `pattern[0 .. i]` that is also a suffix of it.\n
  """
  length: int = len(pattern)
  border_lengths: list[int] = [0 for _ in range(length)]
  border: int = 0
  for index in range(1, length):

    # follow failure links down until the next char matches or we hit 0.
    while border > 0 and pattern[border] != pattern[index]:
      border = border_lengths[border - 1]
    if pattern[border] == pattern[index]:
      border += 1

    # record the border length for this prefix.
    border_lengths[index] = border
  return border_lengths

def kmp_match(text: str, pattern: str) -> list[int]:
  """
    Every shift `s` where `pattern` occurs in `text`, in increasing order.\n
    An empty pattern matches at every position `0 .. len(text)`.\n
  """
  text_length: int = len(text)
  pattern_length: int = len(pattern)
  if pattern_length == 0:
    return list(range(text_length + 1))

  borders: list[int] = prefix_function(pattern)
  shifts: list[int] = []
  matched: int = 0
  for index in range(text_length):

    # mismatch: slide the pattern via the longest border, text stays put.
    while matched > 0 and pattern[matched] != text[index]:
      matched = borders[matched - 1]
    if pattern[matched] == text[index]:
      matched += 1

    # full match: record the shift, then fall back to find overlaps.
    if matched == pattern_length:
      shifts.append(index - pattern_length + 1)
      matched = borders[matched - 1]
  return shifts

Building the failure function by hand

Run $\text{Prefix-Function}$ on $P=\text{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]=\text{A}$ with $P[1]=\text{B}$ — no match, and $k$ is already $0$, so $\pi [1]=0$.
• $i=2$: compare $P[0]=\text{A}$ with $P[2]=\text{A}$ — match, so $k=1$ and $\pi [2]=1$ (border A).
• $i=3$: compare $P[1]=\text{B}$ with $P[3]=\text{B}$ — match, $k=2$, $\pi [3]=2$ (border AB).
• $i=4$: compare $P[2]=\text{A}$ with $P[4]=\text{A}$ — match, $k=3$, $\pi [4]=3$ (border ABA).
• $i=5$: compare $P[3]=\text{B}$ with $P[5]=\text{C}$ — mismatch. Fall back: $k\leftarrow \pi [2]=1$; compare $P[1]=\text{B}$ with C — mismatch again. Fall back: $k\leftarrow \pi [0]=0$; compare $P[0]=\text{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]=\text{A}$ with $P[6]=\text{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$.

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:

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

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

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=\text{ABABACA}$ against $T=\text{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]=\text{C}$ vs $T[5]=\text{B}$ — mismatch. Fall back $q\leftarrow \pi [4]=3$: the border ABA of the matched ABABA is still a live partial match, ending where we stand. Now $P[3]=\text{B}$ matches $T[5]$, so $q=4$. The text pointer never moved; $T[3..4]$ was never re-read.
• $i=6$: $P[4]=\text{A}$ matches, $q=5$.
• $i=7$: $P[5]=\text{C}$ matches, $q=6$.
• $i=8$: $P[6]=\text{A}$ matches, $q=7=m$ — report an occurrence at shift $i-m+1=2$ (indeed $T[2..8]=\text{ABABACA}$), then reset $q\leftarrow \pi [6]=1$ so an overlapping occurrence starting with the final A stays catchable.
• $i=9$, $10$: $P[1]=\text{B}$ and $P[2]=\text{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.

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.

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..r-1]=S[0..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]\leftarrow \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])$.

The case split hides the whole efficiency argument, so make it explicit. When $i<r$, the box guarantees $S[i..r-1]=S[i-l..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..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$.)

A full trace

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

• $i=1$: box empty; compare fresh: $S[0]=\text{a}=S[1]$, then $S[1]=\text{a}\ne S[2]=\text{b}$. $Z[1]=1$, box $[1,2)$.
• $i=2$, $3$: fresh compares fail at once ($\text{b}\ne \text{a}$, $\text{c}\ne \text{a}$): $Z[2]=Z[3]=0$.
• $i=4$: fresh: aab matches, then $S[3]=\text{c}\ne S[7]=\text{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]=\text{a}$, $S[6]=\text{b}\ne S[1]=\text{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, $\text{x}\ne \text{a}$, $Z[7]=0$.
• $i=8$: fresh: aa matches, $S[2]=\text{b}\ne S[10]=\text{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]=\text{a}=S[10]$ — a hit past the old box — then $S[2]=\text{b}\ne S[11]=\text{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 ($\text{z}\ne \text{a}$... precisely $S[1]=\text{a}\ne S[11]=\text{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.

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

def z_function(string: str) -> list[int]:
  """
    The Z-array of `string`. `Z[0]` is set to the string length by\n
    convention; for `i > 0`, `Z[i]` is the length of the longest prefix of\n
    `string` that also starts at position i.\n
  """
  length: int = len(string)
  if length == 0:
    return []

  # Z[0] is the whole string by convention.
  prefix_match: list[int] = [0 for _ in range(length)]
  prefix_match[0] = length

  # [box_left, box_right) is the rightmost known prefix-matching interval.
  box_left: int = 0
  box_right: int = 0

  for index in range(1, length):

    # inside the box: the mirror position gives a free lower bound.
    if index < box_right:
      prefix_match[index] = min(box_right - index, prefix_match[index - box_left])

    # extend the match character by character past the box.
    while (
      index + prefix_match[index] < length
      and string[prefix_match[index]] == string[index + prefix_match[index]]
    ):
      prefix_match[index] += 1

    # if the match reaches further right than the box, advance the box.
    if index + prefix_match[index] > box_right:
      box_left = index
      box_right = index + prefix_match[index]
  return prefix_match

def z_match(text: str, pattern: str, sentinel: str = "\x00") -> list[int]:
  """
    Every shift `s` where `pattern` occurs in `text`, in increasing order.\n
    Runs `z_function` on `pattern + sentinel + text`; the sentinel must not\n
    occur in either string so no match straddles the boundary.\n
  """
  pattern_length: int = len(pattern)
  if pattern_length == 0:
    return list(range(len(text) + 1))

  combined: str = pattern + sentinel + text
  prefix_match: list[int] = z_function(combined)

  # scan only the text portion; a full-length prefix match is an occurrence.
  return [
    index - pattern_length - 1
    for index in range(pattern_length + 1, len(combined))
    if prefix_match[index] >= pattern_length
  ]

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..\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=\text{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.

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