String Matching: Rabin–Karp, KMP & Z

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..n-1]$ and a pattern $P[0..m-1]$ over some alphabet $\Sigma$, report every shift $s$ such that $P$ occurs in $T$ starting at position $s$, i.e. $T[s..s+m-1]=P$. There are $n-m+1$ candidate shifts, and the art is to test them without paying $m$ comparisons apiece.

The naive answer does pay that price. The three algorithms in this lesson each remove the redundancy in a different way: Rabin–Karp replaces a length-$m$ comparison by a length-$1$ hash update, KMP remembers what a partial match already told us so it never backs up over the text, and the Z-function computes a global longest prefix-match array that subsumes both.

The naive scan, and why it wastes work

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

The outer loop runs $n-m+1$ times and the inner loop up to $m$, so the worst case is $\Theta ((n-m+1)m)=O(nm)$, realized by $T=\text{aaaa...a}$ and $P=\text{aaa...ab}$, where every alignment matches $m-1$ characters before failing. 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.¹ The pathology is repetitive patterns, and the cure is to stop discarding what a partial match revealed. The asymptotic gap between the worst and average cases is exactly what the next three algorithms close.

Rabin–Karp: matching by rolling hash

Rabin–Karp turns are these $m$ characters equal? into are these two numbers equal? by hashing 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..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).

The trick 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]$:

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

Rabin–Karp shines when you need to match 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.²

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.

The prefix table, concretely

Here is the full table for $P=\text{ABABACA}$. Read it left to right: $\pi [i]$ is the length of the longest border of the prefix ending at column $i$.

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

Each character of $S$ is examined a constant number of times because the inner while only ever advances $r$, which moves monotonically from $0$ to $\ell$. This is the same amortised argument as KMP, giving $O(\ell )$.

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

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.
• Rabin–Karp compares a rolling hash of each length-$m$ window, updated in $O(1)$ via $h^{\prime }=(b(h-T[s]b^{m-1})+T[s+m])\mathrm{mod}q$, then verifies on hash matches to kill collisions: expected $O(n+m)$, worst case $O(nm)$. Best for many-pattern search.
• 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 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 in linear time — two encodings of a string's self-similarity. KMP/Z give worst-case guarantees; Rabin–Karp trades that for simplicity and multi-pattern flexibility.