Knuth-Morris-Pratt

Suppose you want to find every occurrence of the word "ABAB" inside a long document. The obvious way: line up the pattern at position 0, compare character by character until either a mismatch or a full match, then slide the pattern one position forward and repeat.

This naive approach is simple, but it wastes work. When you shift one position, you throw away everything you just learned about the characters you already read. In the worst case — think of searching "AAAA…AAAB" for "AAAB" — every shift re-reads almost the entire pattern against nearly the same text, blowing up to $O(n \times m)$ comparisons.

In 1977, Donald Knuth, Vaughan Pratt and James Morris published an algorithm that makes the cost exactly $O(n + m)$ — linear in the total length of text and pattern combined. The key insight: after a mismatch, the pattern itself tells you how far you can safely jump without missing any match. That self-knowledge lives in a precomputed failure function (also called the partial-match table), and once you have it, the search never moves the text pointer backwards.

KMP belongs to the solved class — it is a deterministic polynomial-time algorithm (in fact linear time) with a complete correctness proof. No open questions remain about its fundamental complexity.

Type a pattern and some text below. The demo shows the failure function table and then animates the search step by step — watch how the text pointer always moves forward while the pattern pointer jumps using the table.

<div class="controls">
  <label>{{lbl_pattern}} <input id="pat" type="text" value="ABABC" maxlength="12" spellcheck="false"></label>
  <label>{{lbl_text}} <input id="txt" type="text" value="ABABABABC" maxlength="40" spellcheck="false"></label>
  <div class="btns">
    <button id="btnStep" type="button">{{btn_step}}</button>
    <button id="btnRun" type="button">{{btn_run}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<section class="panel">
  <h3>{{h_fail}} <span class="label">{{h_fail_desc}}</span></h3>
  <div id="failTable" class="fail-table"></div>
</section>
<section class="panel">
  <h3>{{h_search}} <span class="label">{{h_search_desc}}</span></h3>
  <div id="searchViz" class="search-viz"></div>
  <div class="status" id="status">{{status_init}}</div>
</section>
<div id="matches" class="matches"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem .9rem; align-items: flex-end; margin-bottom: .8rem; }
label { display: flex; flex-direction: column; gap: .2rem; font-size: .82rem; font-weight: 600; color: #555; }
input { font: 600 15px ui-monospace, monospace; padding: .35rem .6rem; border: 1.5px solid #bcc; border-radius: 6px; width: 180px; }
.btns { display: flex; gap: .5rem; align-items: flex-end; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1.5px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.panel { margin-bottom: .8rem; }
h3 { font-size: .88rem; font-weight: 700; color: #1d3557; margin: 0 0 .3rem; }
.label { font-weight: 400; color: #666; font-size: .78rem; margin-left: .4rem; }
/* {{c_fail_table}} */
.fail-table { display: flex; gap: 3px; flex-wrap: nowrap; }
.ft-col { display: flex; flex-direction: column; align-items: center; gap: 2px; }
.ft-idx { font-size: .72rem; color: #999; width: 32px; text-align: center; }
.ft-char { width: 32px; height: 32px; display: flex; align-items: center; justify-content: center;
           font: 700 14px ui-monospace, monospace; border-radius: 5px;
           background: #e8eef3; border: 1.5px solid #c8d5e0; color: #1d3557; }
.ft-val { width: 32px; height: 24px; display: flex; align-items: center; justify-content: center;
          font: 600 12px ui-monospace, monospace; color: #c0392b; }
/* {{c_search_viz}} */
.search-viz { position: relative; overflow-x: auto; padding-bottom: .4rem; }
.sv-row { display: flex; gap: 3px; margin-bottom: 3px; }
.sv-cell { width: 30px; height: 30px; display: flex; align-items: center; justify-content: center;
           font: 600 13px ui-monospace, monospace; border-radius: 5px; flex-shrink: 0; }
.sv-cell.txt   { background: #e8eef3; border: 1.5px solid #c8d5e0; color: #1d3557; }
.sv-cell.pat   { background: transparent; border: 1.5px solid transparent; color: #555; }
.sv-cell.match { background: #c8f5d8; border-color: #3cb371; color: #1a6a3a; }
.sv-cell.mismatch { background: #fde; border-color: #e05; color: #900; }
.sv-cell.active { border-color: #e67e22; background: #fff3e0; }
.sv-cell.done   { background: #d0ebff; border-color: #3a86ff; color: #1a4a8a; }
.sv-cell.empty  { border-color: transparent; }
.status { font-size: .92rem; font-weight: 600; margin: .3rem 0; min-height: 1.3em; color: #333; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.matches { font-size: .88rem; color: #1d3557; font-weight: 600; min-height: 1.2em; }

// Code not found

Notice the asymmetry: the failure function is computed once from the pattern in $O(m)$ time. The search then scans the text left to right in $O(n)$ time. When a mismatch occurs mid-pattern, instead of sliding one position and re-reading from the start, KMP consults the table and jumps the pattern pointer to the longest prefix that is still a valid suffix of the matched portion — often skipping several positions at once.

Status: solved (Knuth, Morris, Pratt, 1977)

Let the text have length n and the pattern length m.

• Naive search uses $O(n \times m)$ comparisons in the worst case. For a 10 MB file and a 1 000-character pattern that is 10 billion operations.
• KMP builds the failure function in $O(m)$ time and $O(m)$ space. The table f[i] stores the length of the longest proper prefix of the pattern's first i characters that is also a suffix of those same characters.
• KMP searches in $O(n)$ time. The proof uses an amortized argument: define a potential equal to the current position in the text. Each comparison either advances the text pointer (increasing potential) or advances the pattern pointer backwards (decreasing it, but only as much as it was previously increased). Thus the total number of comparisons is at most 2n.
• Combined: $O(n + m)$, which is optimal — you must read every character of the text at least once.

The failure function is the heart of the algorithm. Consider the pattern "ABABC":

At index 3 the value is 2, meaning that if a mismatch occurs right after matching the first four characters "ABAB", the pattern can jump back to position 2 (not position 0) — because "AB" is both a prefix and a suffix of "ABAB". This is the skip that makes KMP linear.

KMP is closely related to pattern matching and sits at the efficient end of the string-search landscape alongside Boyer-Moore and Aho-Corasick.

Linear-time pattern matching turns out to be needed everywhere text exists:

• Text editors and IDEs: every "Find" command is a pattern search. With KMP, finding "function" in a megabyte source file takes one pass, not $O(n \times m)$.
• Bioinformatics: DNA sequences can be gigabytes long. Searching for a gene motif across a whole genome requires exactly the kind of linear-time guarantee KMP provides.
• Network intrusion detection (IDS/IPS): systems like Snort scan millions of packets per second for known malicious signatures. The Aho-Corasick algorithm — a generalization of KMP to multiple patterns — is the standard here.
• Data compression: LZ77 and related algorithms search for repeated substrings; fast pattern matching is at their core.
• Command-line tools: grep, ripgrep and similar tools combine Boyer-Moore-Horspool or SIMD-accelerated variants of these ideas for practical speed on modern hardware.

Explore related ideas in sequence alignment (where patterns can have gaps) and sorting lower bound (another proof that a linear scan can be optimal).

The Knuth-Morris-Pratt algorithm is a masterclass in amortized thinking. Instead of asking "how fast is each step?" it asks "how many steps can possibly happen in total?" — and answers with a simple potential argument that caps the work at 2n comparisons.

The lesson generalises far beyond strings: when an algorithm backtracks, it is paying twice for work it already did. Finding a way to encode what you have learned — as KMP does with its failure function — can turn a quadratic process linear. That principle shows up in everything from dynamic programming to the union-find data structure.

Next time a search box finds your query in a millisecond across millions of lines of code, KMP (or one of its descendants) is probably the reason why.