String matching is the problem of finding all occurrences of a pattern P (length m) inside a text T (length n). The naive approach is O(n·m), and the algorithms in this unit all reach O(n + m) by remembering what earlier comparisons already proved.
The Naive Baseline
Compare the pattern at every text position, and on a mismatch restart from the next position. If most characters match early on, this is effectively O(n·m):
T = AAAAAAAAAAAAAAAAAB (n = 17)
P = AAAAB (m = 5)
→ every shift fails on the very last character: 13 shifts × 5 comparesThree Ways to Beat the Baseline
| Algorithm | Idea | Worst case | Extra space |
|---|---|---|---|
| KMP | LPS table skips redundant comparisons after a mismatch | O(n + m) | O(m) |
| Rabin-Karp | Compare rolling hashes, verify only on collision | O(n·m) (O(n+m) avg) | O(1) |
| Z-Algorithm | Z-array over P$T detects matches via prefix matches | O(n) | O(n) |
KMP — the prefix function
The key realization: when a mismatch occurs at pattern index j, the prefix P[0..j-1] has already matched the text. Some suffix of that prefix is also its prefix — so we can shift the pattern so that those characters line up, without re-comparing them. The LPS table stores exactly those lengths.
Rabin-Karp — hashing the window
Instead of comparing characters, hash the pattern and each text window with a polynomial rolling hash. O(1) per slide. Average case is O(n + m); the pathological case (all windows colliding) degrades to O(n·m). Crucially, Rabin-Karp extends to multi-pattern search: a window hash can be compared against a dictionary of pattern hashes in one lookup.
The Z-algorithm — the Z-box invariant
Over the string P$T, z[i] = length of the longest prefix match starting at i. When i is inside the current rightmost matching box [l, r], seed z[i] from z[i - l] and extend. Because the box’s right edge only moves right, total work is linear. The Z-array is a reusable primitive that appears again in Manacher’s algorithm for palindromes.
Choosing the Right Algorithm
- Single pattern, guaranteed worst case → KMP or Z.
- Multiple patterns (e.g. a dictionary) → Rabin-Karp.
- You need O(n) worst case and minimal code → Z-algorithm.
- Short patterns or small texts → naive is often fastest in practice; the constant factor of the fancy algorithms outweighs their asymptotics.
Deeper Connections
- KMP’s prefix function and the Z-array can be converted into each other in linear time — they encode the same information.
- Rolling hashing generalizes to fingerprinting (document similarity, deduplication).
- The “remember what the previous comparisons proved” idea recurs in the Knuth-Morris-Pratt line of text algorithms and in suffix-array/string-search tooling.