When is KMP not worth using over a naive substring scan in production?

## Worst case is not behaviour The strongest reason KMP loses in practice is that the thing it fixes rarely happens. Naive substring search is O(n*m) in the worst case, but that bound describes a specific pathological shape: text and pattern that agree over long stretches. Over varied data — log lines, prose, mixed binary records — a mismatch typically arrives within the first character or two of a window, so the scan does about n comparisons plus change. Big-O is an upper bound; an O(n*m) label does not say the algorithm ever exhibits that behaviour on your input, and treating the label as a prediction is the single most common mistake in this conversation. ## What KMP actually charges you - **Preprocessing per pattern, O(m).** Irrelevant when one fixed signature scans terabytes; material when a service is handed a fresh user-supplied pattern per request and each document is short. In that regime you may spend as long building the table as scanning. - **Memory, O(m).** Small in absolute terms, but it is a per-pattern allocation on a hot path, and if patterns are many and short-lived it is allocation churn for no gain. - **A worse inner loop.** The naive inner loop is compare, advance, branch — trivially predictable and friendly to fast bulk character-search primitives that hardware and runtimes provide. KMP's mismatch path adds a table read whose value is data-dependent, so the loop is less predictable and cannot be reduced to "find the next occurrence of the first character, then compare". Constants matter, and here the constant moves against you. - **Nothing sublinear on offer.** KMP inspects effectively every text character. Skip-based matchers of the Boyer-Moore family can leap over stretches of text and often run several times faster on typical inputs with medium-length patterns — at the price of a worse worst case than KMP's. - **Maintenance.** A hand-written prefix table is a classic off-by-one habitat, and its failure mode is silence: the matcher returns fewer occurrences rather than crashing. Weigh a bespoke matcher in your codebase against a well-tested standard scan that the whole team already trusts. ## When the guarantee is the product Flip the analysis and KMP is the obvious call in three situations. **Self-similar data.** Periodic binary payloads, long runs of a padding byte, protocol frames that repeat a header motif — precisely the shape that makes naive re-scan almost the whole window at every offset. Here the worst case is not hypothetical, it is Tuesday. **Adversarial input.** If the pattern, the text, or both come from outside your trust boundary, an O(n*m) matcher on a request path is an algorithmic-complexity denial-of-service waiting to be found. An attacker submits the degenerate pair and one request burns CPU that should have served thousands. The mitigation is either an input-size cap you can defend or an algorithm with no quadratic case; KMP is the second, and unlike randomized approaches its bound is deterministic, so there is no hash-seed question to answer and no expected-versus-worst asterisk to explain in a review. **Hard latency budgets.** When a component must state a ceiling — a scan that cannot exceed a fixed slice of a frame budget — an algorithm whose cost is bounded by a constant times the input length lets you write the number down. "Fast on typical input" is not a number you can put in a service objective. ## How to answer this out loud The strong answer is a decision rule, not a preference: *default to the well-tested library scan; reach for a linear-guarantee matcher when the input is self-similar or untrusted, or when a bound must be contractual; and measure on real captures before hand-rolling anything.* The weak answer is either "always use KMP, it's O(n+m)" or "never bother, naive is fine" — both replace a workload question with a slogan. If you have a number from a real capture, lead with it; asymptotics decide the tail risk, measurements decide the median.