232: String Matching: Naive Search, KMP, Prefix Function, Z, and Rabin-Karp

Learning outcomes

By the end of this lesson, you can:

explain and apply naive matching in a realistic implementation;
explain and apply borders and prefix function in a realistic implementation;
explain and apply kmp in a realistic implementation;
explain and apply z algorithm in a realistic implementation;
explain and apply rabin-karp in a realistic implementation.

The target is not just being able to name five algorithms. You should be able to state the matching contract, choose an approach that fits the constraints, explain its invariant, and recognize when a hash-based or deterministic shortcut changes the failure modes.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to locate, filter, compare, or scan text. It might have been a small validation helper, a log search, a parser, or a feature that eventually needed an index. The point is to connect the algorithm to a real constraint rather than memorize a sequence of steps.

The goal is not to memorize terminology. It is to make a defensible decision inside an interview-sized problem and a production data-processing problem. That means reasoning from input size, required guarantees, matching semantics, and failure tolerance instead of reaching for a template before understanding the contract.

Terminology

Naive matching: Try the pattern at each possible start, giving O(nm) worst-case time but simple code and good enough for small inputs. The implementation compares characters directly and has no preprocessing phase.
Borders and prefix function: A border is a proper prefix of a string that is also a suffix of that string. KMP preprocesses the pattern so a mismatch jumps to the longest such border, avoiding rechecking text characters already known to match. The prefix function records the length of that border for every pattern prefix.
KMP: After O(m) preprocessing, scan the text in O(n), giving O(n+m) deterministic worst-case matching. On a mismatch, the prefix table determines how far the pattern can move without discarding information already established.
Z algorithm: The Z-array records the longest substring starting at each position that matches the global prefix. Concatenating pattern + separator + text yields linear-time matching because a Z value at a text position equal to the pattern length identifies an occurrence.
Rabin-Karp: Rolling hashes compare substring hashes in O(1) after each update, but collisions require verification or carefully managed double/mod hashing when correctness cannot tolerate false positives. A matching hash is a candidate, not automatically proof that the strings are equal.
Real text search: Unicode normalization, case/locale, tokenization, fuzzy matching, and indexing change production search requirements; KMP is not a replacement for full-text search systems. Searching bytes, code points, grapheme clusters, normalized text, and locale-aware words are different contracts.

One notation convention helps throughout the lesson: n is the text length and m is the pattern length. Unless a section says otherwise, matching means exact, contiguous matching, and an occurrence is identified by its starting index. Empty-pattern behavior must be chosen explicitly because libraries and interview problems do not all make the same choice.

Mental model

Treat String Matching: Naive Search, KMP, Prefix Function, Z, and Rabin-Karp as a design problem with observable inputs, outputs, invariants, and failure modes. At the simplest level, the task is to determine whether a pattern occurs in a text or to report the positions where it occurs. The algorithms differ in what information they keep when a comparison fails.

Naive matching throws away all information about the failed alignment and starts again at the next possible position. Borders and the prefix function retain structure inside the pattern. KMP uses that structure while scanning the text. The Z algorithm organizes equivalent prefix comparisons around a reusable matching window. Rabin-Karp retains a compact numerical summary of each window, which is fast to update but can collide.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. For exact matching, that usually means a reported index has exactly m consecutive characters equal to the pattern, and no index is reported merely because a shortcut produced a plausible candidate. Then choose the mechanism that enforces that invariant.

Deep dive

1. Naive matching

The naive algorithm tries the pattern at every possible start in the text. At a candidate start, it compares the pattern from left to right until either a character differs or the entire pattern matches. If the text has length n and the pattern has length m, there are at most n - m + 1 candidate starts, and each can require m comparisons. The worst-case time is therefore O(nm), with O(1) extra space.

That worst case is real: a text and pattern with long repeated prefixes can cause nearly the same successful comparisons at many neighboring starts. The trade-off is that the code is direct, easy to test, and often fast enough when the inputs are small or the first mismatch usually occurs early.

Decision rule: Use naive matching deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. It is also a reasonable baseline implementation for testing KMP, Z, or Rabin-Karp: a simple reference implementation gives you something trustworthy to compare against on random and adversarial inputs.

2. Borders and prefix function

The difficulty KMP solves appears when a partial match fails. Suppose the pattern has already matched through position j - 1, but the next text character does not match pattern position j. The matched portion may itself end with a prefix of the pattern. If so, shifting the pattern to that border preserves useful work instead of comparing those characters again.

A border of a string is both a prefix and a suffix, but it must be proper: it cannot be the whole string. For example, abab has the border ab. The prefix function, commonly written pi, stores for each pattern position i the length of the longest proper prefix of pattern[0..i] that is also a suffix of that substring. A mismatch can then follow the chain pi[j - 1] until either a compatible character is found or the candidate length reaches zero.

The key invariant is: after processing pattern[0..i], pi[i] describes the longest valid border of exactly that prefix. Maintaining this invariant makes the later KMP scan mechanical. The prefix-function construction itself runs in O(m) time and uses O(m) storage because each fallback moves to a shorter border rather than restarting a full comparison.

This is where people usually get confused: a prefix function is not a table of positions where the pattern occurs in the text. It describes internal repetition in the pattern, before the text is scanned. That distinction is why the same table can be reused for many texts when the pattern is fixed.

Decision rule: Use borders and prefix function deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. When debugging, print the pattern beside its pi values and verify a few prefixes by hand; an incorrect fallback value usually becomes visible there before it causes a confusing text-scan result.

3. KMP

KMP combines the prefix function with a single left-to-right text scan. Keep j, the number of pattern characters currently matched. For each text character, compare it with pattern[j]. On a mismatch, replace j with the prefix-function fallback and try again without moving the text index backward. On a match, increment j; when j === m, report the occurrence and fall back to pi[m - 1] if overlapping matches are required.

The scan is linear because the text pointer only moves forward, while j can fall only through previously computed borders. After O(m) preprocessing, the text scan is O(n), giving O(n+m) deterministic worst-case matching and O(m) additional storage. If the API returns only the first match, it can stop at the first report; if it returns all matches, falling back after a match is what preserves overlaps such as finding aba twice in ababa.

There are boundary decisions to make before implementing it. If m > n, no non-empty pattern can occur. If the pattern is empty, define whether the result is index 0, every boundary between characters, or a rejected input; do not let an accidental array access decide. If matching Unicode text, also define whether indexes refer to JavaScript UTF-16 code units, Unicode code points, or user-perceived grapheme clusters.

Decision rule: Use kmp deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. KMP is a strong choice when worst-case guarantees matter, the match is exact, and preprocessing the pattern is acceptable. It does not solve normalization, tokenization, fuzzy search, or ranking.

4. Z algorithm

The Z-array provides another way to reuse prefix comparisons. For a string s, z[i] is the length of the longest substring beginning at i that is equal to the prefix beginning at 0. Usually z[0] is defined as 0 or as the string length by convention; the implementation and tests must agree.

To search for a pattern, build a combined string such as pattern + separator + text, where the separator cannot occur in either input under the chosen representation. A position in the text portion with z[i] === m means the pattern matches there. The standard linear implementation maintains a window [left, right) known to match the prefix. If the current index lies inside that window, it copies a bounded amount of previously computed information before extending with direct comparisons. The window never moves backward, which gives O(n+m) time and O(n+m) storage.

The separator is not decorative. If it can occur in the pattern or text, a prefix match could cross the boundary and produce an invalid result. For arbitrary input, use a representation or sentinel strategy that makes this impossible; do not silently assume a punctuation character is absent. The Z algorithm and KMP have the same linear asymptotic bound, but their tables and natural applications differ. Z is especially convenient when many prefix matches or the structure of one combined string is the object of interest.

Decision rule: Use z algorithm deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. When debugging, inspect the [left, right) window and confirm that every copied Z value is clipped to the current window; copying an unbounded value is a common source of incorrect results.

5. Rabin-Karp

Rabin-Karp turns each length-m window into a hash and compares that hash with the pattern hash. With a polynomial rolling hash, moving from one window to the next removes the outgoing character's weighted contribution, shifts the remaining value, and adds the incoming character. With suitable arithmetic, the update is O(1), so scanning all windows is O(n) expected time in the usual average-case discussion, with O(m) preprocessing and O(1) or O(m) extra storage depending on what is retained.

The subtle failure mode is a collision: different strings can have the same hash. A hash equality therefore identifies a candidate. If correctness matters, compare the candidate substring with the pattern before reporting it. Double hashing or carefully chosen modular arithmetic can make accidental collisions very unlikely, but it does not change the logical distinction between a probabilistic filter and an exact verification step. Integer overflow, negative modulo behavior, and character encoding also need explicit treatment in a real implementation.

Rabin-Karp becomes attractive when comparing many windows, looking for multiple patterns, or using hashes as a cheap preliminary filter. Its worst-case behavior can degrade when many candidates collide or when verification is frequent. It is not automatically better than KMP just because each rolling update is constant time.

Decision rule: Use rabin-karp deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State whether the API accepts a tiny probability of a false candidate, verifies every hash match, or uses hashing only as an optimization before an exact comparison. That sentence determines whether the algorithm is safe for the caller's requirements.

6. Real text search

Exact substring matching is only one interpretation of “search.” Unicode normalization can make visually equivalent text have different representations. Case conversion can be locale-sensitive. Tokenization changes whether punctuation and word boundaries matter. Fuzzy matching introduces distance or ranking rules, and indexing changes the problem from scanning one string to querying a maintained data structure.

These choices belong in the matching contract. Decide what the user means by a character, whether case and accents matter, whether matches may cross tokens, and whether results need ranking. Normalize consistently before applying an exact algorithm if normalization is part of the requirement, and remember that transformed text may change index mapping back to the original text.

Unicode normalization, case/locale, tokenization, fuzzy matching, and indexing change production search requirements; KMP is not a replacement for full-text search systems.

Decision rule: Use real text search deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. A production system may need a search engine, an inverted index, or a locale-aware library rather than a hand-written substring scan. The right choice depends on semantics and workload, not on the fact that KMP has a better worst-case bound than naive matching.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. For the interview version, you might be asked to find every occurrence of a pattern, including overlaps. For the production version, you might scan large log batches or documents where memory limits, encoding, normalization, and predictable latency matter. The surface request is similar, but the contracts are not automatically identical.

Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. For example: “Return every starting index where the exact pattern occurs in the text, including overlapping matches; reject an undefined empty-pattern contract.” Then state the invariant: every returned index has a complete exact match, and the algorithm never treats a hash collision or a boundary-crossing prefix as proof of a match.

The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but makes edge cases much harder to reason about. A string algorithm can be correct while the surrounding system still searches the wrong normalized representation or reports indexes in the wrong coordinate system.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

This small function is not a string matcher; it is a reminder about the discipline being applied. Its state is intended to represent the best value seen so far. The code also exposes an important contract question: returning 0 for an empty array is only correct if the problem defines that identity value. A string-search implementation has the same kind of boundary decision for an empty pattern, a missing input, or an invalid separator.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For a matcher, the normal path should include both a match and a no-match result; the empty case should exercise the documented contract; repeated or overlapping matches should confirm that occurrences are not accidentally skipped; and a dependency failure should be relevant when the search is part of a service or data pipeline. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For string matching specifically, ask whether a document can exceed memory limits, whether input arrives as chunks, whether indexes remain meaningful after normalization, and whether worst-case latency is an operational requirement.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence. A linear algorithm can still be the wrong design if constructing a combined string duplicates a huge input, if the required semantics are locale-aware, or if a maintained index would answer repeated queries more efficiently.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Do not treat a client-side search result as authorization, and do not log sensitive text merely because it made debugging easier.

Guided lab

Implement KMP and one rolling-hash search. Print the prefix/Z structure for a patterned string, create an intentional small-modulus hash collision, and show why candidate verification is required. Compare both implementations with a naive reference on cases containing no match, repeated prefixes, overlapping matches, a pattern longer than the text, and the empty-pattern contract you selected.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the collision experiment, choose a deliberately small modulus and find two different windows with the same hash. The expected observation is not that Rabin-Karp is unusable; it is that the hash comparison narrows the candidates and exact comparison preserves correctness. When a test fails, print the pattern, text window, hash values, and verification result rather than only printing “false.”

Edge cases and failure modes

Naive matching: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include repeated-prefix inputs that expose the O(nm) worst case.
Borders and prefix function: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Check patterns with no border, a border of length one, nested borders, and a border that is shorter than the immediately preceding candidate.
KMP: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify overlapping matches, fallback after a mismatch, pattern-longer-than-text behavior, and the chosen empty-pattern result.
Z algorithm: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Test repeated prefixes, a separator appearing unexpectedly, the z[0] convention, and matches adjacent to the concatenation boundary.
Rabin-Karp: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Test intentional collisions, modular arithmetic boundaries, verification of candidates, and inputs whose encoding changes the character-to-index relationship.

Across all five approaches, also test whether the requested result is the first occurrence, all occurrences, or only a boolean. Those APIs have different stopping behavior and different opportunities to mishandle overlaps.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For string matching, common algorithm-specific mistakes include using j - 1 incorrectly when building or consuming the prefix table, forgetting the fallback after a complete KMP match, choosing a separator that can occur in the inputs, and returning a Rabin-Karp candidate without verification. Another recurring error is treating JavaScript string indexes as user-visible character positions without checking whether UTF-16 code units match the product's definition of a character.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Print intermediate prefix values or Z windows for deterministic algorithms. For Rabin-Karp, log hash and exact-comparison outcomes in a controlled test, while avoiding sensitive production text in logs.

Interview questions

What problem does Naive matching solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Borders and prefix function solve, and what trade-off or failure mode would make you choose a different approach?
What problem does KMP solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Z algorithm solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Rabin-Karp solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than quote Big-O notation. State the matching semantics, the invariant, the extra storage, the relevant worst-case behavior, and at least one boundary case. A senior-level answer distinguishes a deterministic guarantee from an expected or probabilistic one and distinguishes exact substring search from production full-text search.

Checkpoint

Without notes, explain String Matching: Naive Search, KMP, Prefix Function, Z, and Rabin-Karp to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

As a self-check, you should be able to explain why naive matching can repeat work, how a border preserves that work, how KMP uses the prefix function without moving the text pointer backward, why the Z separator must be safe, and why a Rabin-Karp hash match is not sufficient by itself. If any of those explanations is missing, return to the corresponding section rather than relying on the final implementation to hide the gap.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.