Finding a pattern in a text without ever backing up in the text — three algorithms that all reach O(n + m) by remembering what a partial match already told them.
Given a text T of length n and a pattern P of length m, find every position where P occurs in T. The naive algorithm tries every alignment and costs O((n-m+1)m). The chapter’s three improvements all share one insight: a failed comparison is information, and throwing it away is what makes the naive method slow. Rabin-Karp uses hashing, finite automata precompute a state machine, and Knuth-Morris-Pratt precomputes how far the pattern can safely slide.
P is a prefix of T is written P ⊑ T, and the pattern occurs with shift s if T[s+1 : s+m] = P[1 : m].NAIVE-STRING-MATCHER(T, P, n, m)
1 for s = 0 to n - m
2 if P[1:m] == T[s+1 : s+m]
3 print "Pattern occurs with shift" sO((n-m+1)m), which is Θ(n²) when m = n/2. No preprocessing, and correct.
T = aaaaaaaab and P = aaab, every alignment matches three characters and fails on the fourth — then the algorithm slides by one and re-examines characters it has already seen. It forgets everything it learned. All three better algorithms are about not forgetting.m window of the text as a number and compare it with the pattern’s number. Comparing two integers is O(1), and the next window’s value can be computed from the current one in O(1) with a rolling hash: subtract the departing digit, shift, add the arriving digit.ts+1 = d · ( tₛ - T[s+1] · h ) + T[s+m+1] (mod q)
where d = radix, h = dm-1 mod q, and q is a primeEverything is reduced modulo a prime q so the values fit in a machine word.
| Case | Time |
|---|---|
| Preprocessing | Θ(m) |
| Expected matching | O(n + m) with a good prime |
| Worst case | O((n-m+1)m) — every window hashes equal |
k pattern hashes into a hash table and scan the text once, checking each window’s hash against the set. That finds all k patterns in O(n + km) expected, which KMP cannot do without k separate passes. It is also the basis of document fingerprinting and plagiarism detection.m + 1 states, where state k means “the last k characters read match the first k characters of the pattern”. Feed the text through it one character at a time; reaching state m means an occurrence.FINITE-AUTOMATON-MATCHER(T, δ, n, m)
1 q = 0
2 for i = 1 to n
3 q = δ(q, T[i]) // one table lookup per character
4 if q == m
5 print "Pattern occurs with shift" i - mMatching is Θ(n) — exactly one table lookup per text character, with no comparisons and no backing up.
The state after reading a prefix is defined by the suffix function σ(x): the length of the longest prefix of P that is also a suffix of x. That is what makes the automaton correct — the state carries exactly the useful information about everything read so far.
| Phase | Cost |
|---|---|
Building δ (naive) | O(m³|Σ|) |
Building δ (improved) | O(m|Σ|) |
| Matching | Θ(n) |
(m+1) × |Σ| entries. For ASCII that is 128 columns; for Unicode it is impractical. This dependence on alphabet size is exactly what KMP removes.Θ(n) matching without building a transition table. Instead of storing where to go for every character, it stores a single prefix function π of m entries that says how far to slide the pattern after a mismatch. Preprocessing drops from O(m|Σ|) to Θ(m), with no alphabet dependence at all.KMP-MATCHER(T, P, n, m)
1 π = COMPUTE-PREFIX-FUNCTION(P, m)
2 q = 0 // characters matched so far
3 for i = 1 to n // scan the text; i never goes backwards
4 while q > 0 and P[q+1] ≠ T[i]
5 q = π[q] // slide the pattern, keep i fixed
6 if P[q+1] == T[i]
7 q = q + 1
8 if q == m
9 print "Pattern occurs with shift" i - m
10 q = π[q] // look for the next occurrencei never decreases. Only the pattern slides. That is the defining property, and it is why KMP works on a stream you cannot rewind — a network socket, a file read forward once.π[q] is the length of the longest proper prefix of P that is also a suffix of P[1:q]. On a mismatch after q matched characters, those π[q] characters are already known to match, so the pattern can slide forward by q - π[q] without re-examining any text.ababaca. Each value says how much of a partial match survives a failure.COMPUTE-PREFIX-FUNCTION(P, m)
1 π[1] = 0
2 k = 0
3 for q = 2 to m
4 while k > 0 and P[k+1] ≠ P[q]
5 k = π[k]
6 if P[k+1] == P[q]
7 k = k + 1
8 π[q] = k
9 return πΘ(m). Note the structure is identical to KMP-MATCHER — it is the pattern matched against itself.
while loop on line 4 can iterate many times in one pass, so the obvious bound is O(nm). But q increases by at most 1 per outer iteration and strictly decreases on every while iteration, and it never goes below 0. So the total number of decreases is bounded by the total number of increases, which is n. This is the potential method from Chapter 16 with Φ = q, and it is the cleanest small application of amortized analysis in the book.| Algorithm | Preprocessing | Matching | Extra space | Notes |
|---|---|---|---|---|
| Naive | 0 | O((n-m+1)m) | O(1) | Fine for tiny inputs |
| Rabin-Karp | Θ(m) | O(n+m) expected, O(nm) worst | O(1) | Best for multiple patterns |
| Finite automaton | O(m|Σ|) | Θ(n) | O(m|Σ|) | Fastest inner loop; alphabet-bound |
| KMP | Θ(m) | Θ(n) | Θ(m) | The default choice |
grep is built on. Aho-Corasick generalises KMP to many patterns at once and drives intrusion detection and virus scanners. This chapter’s value is the ideas — rolling hashes, automaton states, and the prefix function — all three of which reappear in those algorithms.O((n-m+1)m) and its flaw is that it discards what a partial match already proved.O(1). Hash matches must be verified, since spurious hits are possible.O(n+m) expected, O(nm) worst case, and is the right choice for many patterns at once.Θ(n) matching with one lookup per character, but needs an O(m|Σ|) table — impractical for large alphabets.Θ(n) with only Θ(m) preprocessing and no alphabet dependence.π[q] is the longest proper prefix of P that is also a suffix of P[1:q]; a mismatch slides the pattern by q - π[q]. The text index never moves backwards.Φ = q — decreases are bounded by increases.Chapter 33 is the 4th edition’s newest chapter: machine-learning algorithms, covering clustering, multiplicative weights, and gradient descent from an algorithms perspective rather than a statistical one.