String Matching (KMP, Rabin-Karp, Z-Function)

Why this is the roadmap's optional capstone

Every interview that asks "does string t contain pattern p?" has a correct answer you can produce in thirty seconds: slide p across t, compare character by character, restart on mismatch. That's the naive algorithm, it's O(n·m) in the worst case, and for the vast majority of interviews — including most Senior loops — stating it, coding it cleanly, and calling out its complexity is a completely acceptable answer. The gap this subtopic closes is narrow but real: a small number of interviewers, disproportionately concentrated at Google and other algorithm-heavy shops, will respond with "good — now do it without the O(n·m) worst case." This is what lets you answer that follow-up with a derivation instead of a shrug.

The naive algorithm and why it breaks

This is O(n·m): for each of the n - m + 1 starting positions, you may compare up to m characters before finding a mismatch. It's slow specifically when the pattern and text share long repeated substrings — the canonical worst case is text = "aaaaaaaaaaaaaab", pattern = "aaaaab", where almost every starting position matches m - 1 characters before failing on the last one. This is exactly the situation KMP is built to fix: the naive algorithm forgets everything it just learned every time it fails. After matching "aaaaa" and failing on the 6th character, it throws away the fact that it just verified five as and restarts from scratch one position to the right — even though it already knows those next few characters are as too.

KMP: never re-examine a character you've already matched

The core idea: precompute, for the pattern alone, enough information that when a mismatch happens during the text scan, you know exactly how far the pattern pointer can safely jump back — without ever moving the text pointer backward.

The failure function / LPS array

The LPS array (Longest proper Prefix which is also a Suffix — also called the failure function or prefix function) is defined per-pattern: lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. "Proper prefix" means it cannot be the entire substring itself.

Take pattern = "ababc":

i	pattern[0..i]	Proper prefixes	Proper suffixes	Longest match	lps[i]
0	a	(none)	(none)	—	0
1	ab	a	b	—	0
2	aba	a, ab	a, ba	a	1
3	abab	a, ab, aba	b, ab, bab	ab	2
4	ababc	a, ab, aba, abab	c, bc, abc, babc	(none)	0

Building the LPS array in O(m)

The trick to building this in linear time (instead of the O(m²) implied by the table above) is the same self-similarity insight you'll see again in Manacher's algorithm: use previously computed lps values instead of re-scanning from zero.

Why this is O(m) and not O(m²): length only ever increases when i increases (by at most 1 each), and it only decreases via the elif branch, which doesn't advance i at all. Since length can't go below 0 and is bounded above by i, the total number of decrements across the whole run is bounded by the total number of increments — the same amortized argument from Big-O & Complexity Analysis and from Variable-Size Sliding Window's pointer-movement bound.

The search itself

The invariant that makes this correct — and the single most important sentence in this whole subtopic: i never decreases. On a mismatch, instead of restarting the text pointer one position past where it started (as the naive algorithm does), you consult lps to find the longest prefix of the pattern that's guaranteed to already be sitting at the current text position, and resume comparing from there. Since i only ever increases and does so at most n times, and j's total decrements are bounded by its total increments (same amortized argument as build_lps), the whole search is O(n), and combined with the O(m) preprocessing, the full algorithm is O(n + m) — worst case, not average case, with zero risk of collision-driven slowdown.

Rabin-Karp: rolling hashes instead of a failure function

KMP's guarantee comes from clever bookkeeping over exact character comparisons. Rabin-Karp takes a completely different approach: hash every length-m window of the text and compare hashes instead of raw substrings, using a rolling hash so each window's hash is computed from the previous one in O(1).

The rolling hash

Treat the string as a number in some base b (e.g. 31 or 256), modulo a large prime q to keep the numbers bounded:

hash(s[i..i+m)) = (s[i]·b^(m-1) + s[i+1]·b^(m-2) + ... + s[i+m-1]·b^0) mod q

The "rolling" step removes the outgoing character's contribution and adds the incoming one in O(1):

hash(s[i+1..i+1+m)) = ((hash(s[i..i+m)) - s[i]·b^(m-1)) · b + s[i+m]) mod q

This gives O(n + m) average case: computing the pattern hash and first window hash is O(m), and each subsequent window update is O(1), so the scan is O(n). But this bound is probabilistic, not guaranteed — the worst case is still O(n·m) if every window collides.

Collisions are not optional to handle

A hash match is evidence of equality, not proof — two different substrings can hash to the same value (a collision), and an adversarial or unlucky input can make this happen often. Always verify with a direct character comparison after a hash match; this is the single most common correctness bug in Rabin-Karp implementations, and skipping it produces a solution that passes casual testing while being silently wrong. For extra safety against adversarial inputs, use double hashing: compute two independent rolling hashes with different bases/moduli and only treat a match as a candidate when both agree — standard practice in competitive programming, since single-modulus hashing has known adversarial breaks.

Where Rabin-Karp wins

KMP is the better choice when you need an ironclad worst-case guarantee for a single pattern. Rabin-Karp pulls ahead in two situations that come up constantly in Hard-tier interview problems:

• Multi-pattern search. Hash all patterns of the same length into a set once, then slide one window across the text checking set membership — O(n + total pattern length) instead of running KMP once per pattern.
• "Does a substring of length k repeat?"-style problems, where you hash every length-k window and look for a hash collision (verified) across the whole string — the core mechanic behind Longest Duplicate Substring.

Real-world case study: rsync and content-defined deduplication. rsync needs to transfer only the parts of a file that changed since the last sync, without both sides needing to agree in advance on where the "changed" boundaries are — a single byte inserted near the start of a file shifts every fixed-size block boundary after it, which would make naive fixed-size chunking miss almost every match even though the file is 99% identical. The fix is a rolling hash over a sliding window (rsync's original algorithm uses a checksum closely related to Rabin-Karp's), computed cheaply at every byte offset rather than only at fixed block boundaries — this is exactly the O(1)-per-step rolling update this subtopic builds on, just repurposed to find where a known block's content reappears anywhere in the new file, not only at aligned positions. The same rolling-hash-to-find-content-boundaries idea, generalized, is content-defined chunking: the technique deduplication systems (backup tools, some distributed file systems) use to split files into variable-length chunks at hash-determined boundaries, so that inserting a byte near the start of a file only changes the one chunk containing it instead of reshuffling every downstream chunk boundary.

The Z-function: prefix-match information at every position

KMP's lps array only tells you about the pattern matching against itself. The Z-function generalizes this: for a string s of length n, the Z-array is defined so that z[i] is the length of the longest substring starting at i that is also a prefix of the whole string s (by convention z[0] is left undefined or set to n/0 depending on the source — CP-Algorithms leaves it unused).

s = "aabcaabxaaz" 0123456789... z - 1 0 0 3 1 0 0 2 2 0

z[4] = 3 because s[4..] = "aabxaaz" shares a 3-character prefix ("aab") with s itself.

Computing it in O(n)

The algorithm maintains the rightmost previously-found "Z-box" [l, r] — a segment that's known to match a prefix of s — and reuses that information for new positions inside the box, falling back to direct comparison only at or beyond it:

This is the same amortized argument as KMP and Manacher's: the right boundary r only ever advances, and every character comparison inside the while loop either extends r or fails immediately, so total work is O(n).

Using it for pattern search

To find pattern p inside text t, compute the Z-function of p + "#" + t (with # a separator absent from both strings). Any index i in the combined string (past the separator) with z[i] == len(p) marks a match, at text position i - len(p) - 1. This is functionally equivalent to KMP's O(n + m) guarantee, but the Z-array is also directly useful beyond matching — e.g. finding the shortest string whose repetition (possibly with a partial final copy) produces s: the smallest period k such that k divides n and z[k] == n - k (Repeated Substring Pattern is a special case of this idea, and Repeated String Match asks a closely related question).

Choosing between them

Technique	Time	Space	Guarantee	Best for
Naive scan	O(n·m)	O(1)	Always	Interview opener; fine when constraints are tiny
KMP	O(n + m)	O(m)	Worst-case, deterministic	Single-pattern search with a hard worst-case requirement; no collision risk ever
Rabin-Karp	O(n + m) average, O(n·m) worst case	O(1) beyond hashes	Probabilistic (verify on match)	Multi-pattern search; "does any window of length k repeat" problems; combines cleanly with binary search on length
Z-function	O(n + m)	O(n + m)	Worst-case, deterministic	When you need prefix-match length at every position, not just match/no-match (period detection, string compression, some palindrome tricks)

One thing deliberately beyond naive KMP/Rabin-Karp: Aho–Corasick — a trie of all patterns augmented with KMP-style failure links, so one forward pass over the text tracks all patterns simultaneously. The failure links are the same "on mismatch, jump to the longest viable shorter prefix" move as the LPS array, but wired into a trie via BFS at build time. Know the name and the one-sentence idea; implementing it cold is a stretch goal even at the Google bar.

Where AC meets Tries (concrete bridge)

The natural home for AC in this roadmap is the Tries topic's streaming problems — especially Stream of Characters:

• Naive: track a separate trie pointer for every prior stream position → O(Q) per query.
• Constraint cap: no word longer than max_len, so only look back max_len chars in a reversed-word trie → O(max_len) per query (see the Tries subtopic for the code sketch).
• AC upgrade: insert words forward into a trie, build failure links once, maintain one automaton pointer — _go(state, letter) per query, O(1) amortized, no stream buffer.

That progression — active list → bounded lookback → failure links — is the same KMP insight applied three ways. If you understood lps[j - 1] on mismatch, you already understand _go(state, ch) falling back through failure links.

For board + dictionary problems (Word Search II), AC is usually overkill; a single-pattern trie + DFS with early pruning is the interview default. AC pays off when many patterns are searched against one long text in a single left-to-right pass.

Pitfalls and interview gotchas

• Off-by-one in the LPS array. The most common bug: forgetting that lps[i] describes pattern[0..i] inclusive, or advancing i inside the elif length != 0 branch (you must not — only length changes there).
• Forgetting j = lps[j - 1] after a full match, not j = 0, if you want to find overlapping occurrences (e.g. pattern "aa" in text "aaaa" should report 3 matches, not 2).
• Skipping the verification step in Rabin-Karp. A hash collision without a direct-comparison fallback silently produces wrong answers, and this is exactly the kind of bug that survives weak test cases and fails in the interviewer's follow-up "what if these two different strings hash the same?"
• Choosing a bad modulus/base for Rabin-Karp (e.g. a modulus that's not prime, or one small enough that collisions become frequent) — a real, well-known way for hash-based solutions to degrade to O(n·m), and precisely why KMP remains the safer default when a guarantee is explicitly required.
• Confusing the Z-function's z[i] with KMP's lps[i]. They answer related but different questions — lps[i] is about prefix-suffix overlap within a prefix of the pattern, z[i] is about how much of the entire string's prefix reappears starting at i. They're connected (each can be derived from the other) but are not interchangeable in code.