Introduction

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×m)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)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.

Try It

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>Pattern <input id="pat" type="text" value="ABABC" maxlength="12" spellcheck="false"></label>
  <label>Text <input id="txt" type="text" value="ABABABABC" maxlength="40" spellcheck="false"></label>
  <div class="btns">
    <button id="btnStep" type="button">Step</button>
    <button id="btnRun" type="button">Run all</button>
    <button id="btnReset" type="button" class="ghost">Reset</button>
  </div>
</div>
<section class="panel">
  <h3>Failure function <span class="label">f[i] = longest prefix = suffix of pattern[0..i]</span></h3>
  <div id="failTable" class="fail-table"></div>
</section>
<section class="panel">
  <h3>Search <span class="label">text pointer <em>i</em> never goes back</span></h3>
  <div id="searchViz" class="search-viz"></div>
  <div class="status" id="status">Press Step or Run all.</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; }
/* Failure function 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; }
/* 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// KMP: build failure function then search text for pattern.
// The text pointer i never decreases — that’s the whole point.

function buildFailure(pat) {
  const m = pat.length, f = new Array(m).fill(0);
  let k = 0;
  for (let i = 1; i < m; i++) {
    while (k > 0 && pat[k] !== pat[i]) k = f[k - 1];
    if (pat[k] === pat[i]) k++;
    f[i] = k;
  }
  return f;
}

function kmpSearch(txt, pat, f) {
  // Returns array of step objects for animation
  const steps = [], matches = [];
  const n = txt.length, m = pat.length;
  if (!m) return { steps, matches };
  let j = 0; // pattern pointer
  for (let i = 0; i < n; i++) {
    while (j > 0 && pat[j] !== txt[i]) {
      steps.push({ i, j, type: 'mismatch', prevJ: j, newJ: f[j - 1], matches: [...matches] });
      j = f[j - 1];
    }
    if (pat[j] === txt[i]) {
      steps.push({ i, j, type: 'match', matches: [...matches] });
      j++;
    } else {
      steps.push({ i, j: 0, type: 'nomatch', matches: [...matches] });
    }
    if (j === m) {
      const start = i - m + 1;
      matches.push(start);
      steps.push({ i, j, type: 'found', start, matches: [...matches] });
      j = f[j - 1];
    }
  }
  return { steps, matches };
}

// ---------- State ----------
let pat = '', txt = '', f = [], steps = [], stepIdx = -1, allMatches = [];
let running = false;

function init() {
  pat = document.getElementById('pat').value.toUpperCase();
  txt = document.getElementById('txt').value.toUpperCase();
  f = buildFailure(pat);
  const res = kmpSearch(txt, pat, f);
  steps = res.steps; allMatches = [];
  stepIdx = -1;
  renderFailTable();
  renderSearch(-1, null, []);
  document.getElementById('status').textContent = 'Press Step or Run all.';
  document.getElementById('status').className = 'status';
  document.getElementById('matches').textContent = '';
}

function renderFailTable() {
  const el = document.getElementById('failTable');
  el.innerHTML = '';
  for (let i = 0; i < pat.length; i++) {
    const col = document.createElement('div'); col.className = 'ft-col';
    col.innerHTML = `<div class="ft-idx">${i}</div><div class="ft-char">${pat[i]}</div><div class="ft-val">${f[i]}</div>`;
    el.appendChild(col);
  }
}

function renderSearch(iPos, jPos, matches) {
  const el = document.getElementById('searchViz'); el.innerHTML = '';
  if (!txt.length) return;

  // Row 1: text
  const txtRow = document.createElement('div'); txtRow.className = 'sv-row';
  for (let i = 0; i < txt.length; i++) {
    const c = document.createElement('div');
    let cls = 'sv-cell txt';
    if (i === iPos) cls += ' active';
    if (matches.includes('text_' + i)) cls += ' done';
    c.className = cls; c.textContent = txt[i];
    txtRow.appendChild(c);
  }
  el.appendChild(txtRow);

  // Row 2: aligned pattern (show pattern aligned at iPos - jPos)
  if (jPos !== null && jPos >= 0 && iPos >= 0) {
    const offset = iPos - jPos;
    const patRow = document.createElement('div'); patRow.className = 'sv-row';
    for (let i = 0; i < txt.length; i++) {
      const pi = i - offset;
      const c = document.createElement('div');
      if (pi >= 0 && pi < pat.length) {
        let cls = 'sv-cell pat';
        if (pi < jPos) cls += ' match';
        if (pi === jPos) cls += ' active';
        c.className = cls; c.textContent = pat[pi];
      } else {
        c.className = 'sv-cell empty'; c.textContent = '';
      }
      patRow.appendChild(c);
    }
    el.appendChild(patRow);
  }

  // highlight match positions in text
  if (matches.length) {
    for (const start of matches) {
      for (let k = 0; k < pat.length; k++) {
        const cell = txtRow.children[start + k];
        if (cell) { cell.classList.add('done'); }
      }
    }
  }
}

function applyStep() {
  if (stepIdx >= steps.length - 1) return false;
  stepIdx++;
  const s = steps[stepIdx];
  allMatches = s.matches.slice();

  const statusEl = document.getElementById('status');
  const matchEl = document.getElementById('matches');

  if (s.type === 'match') {
    renderSearch(s.i, s.j, allMatches);
    statusEl.textContent = fmt('text[%i%]=’%v%’ = pattern[%j%]=’%v2%’ — match, advance both.', { i: s.i, v: txt[s.i], j: s.j, v2: pat[s.j] });
    statusEl.className = 'status';
  } else if (s.type === 'mismatch') {
    renderSearch(s.i, s.j, allMatches);
    statusEl.textContent = fmt('Mismatch at text[%i%] vs pattern[%j%]. Jump pattern to f[%v%]=%newJ% (no text backtrack!).', { i: s.i, j: s.j, v: s.j-1, newJ: s.newJ });
    statusEl.className = 'status bad';
  } else if (s.type === 'nomatch') {
    renderSearch(s.i, 0, allMatches);
    statusEl.textContent = fmt('text[%i%]=’%v%’ ≠ pattern[0]=’%v2%’ — skip.', { i: s.i, v: txt[s.i], v2: pat[0] });
    statusEl.className = 'status bad';
  } else if (s.type === 'found') {
    renderSearch(s.i, s.j, allMatches);
    statusEl.textContent = fmt('✓ Pattern found at position %start%!', { start: s.start });
    statusEl.className = 'status ok';
  }

  matchEl.textContent = allMatches.length
    ? fmt('Matches found at: %map%', { map: allMatches.map(p => 'position ' + p).join(', ') })
    : '';

  if (stepIdx === steps.length - 1 && s.type !== 'found') {
    if (!allMatches.length) {
      statusEl.textContent = 'Search complete — pattern not found.';
      statusEl.className = 'status bad';
    } else {
      statusEl.textContent = fmt('Search complete — %length% match(es):: positions %allMatches%.', { length: allMatches.length, allMatches: allMatches.join(', ') });
      statusEl.className = 'status ok';
    }
  }
  return true;
}

document.getElementById('btnStep').addEventListener('click', () => { if (!running) applyStep(); });
document.getElementById('btnRun').addEventListener('click', async () => {
  if (running) return;
  running = true;
  while (applyStep()) await new Promise(r => setTimeout(r, 280));
  running = false;
});
document.getElementById('btnReset').addEventListener('click', init);
document.getElementById('pat').addEventListener('input', init);
document.getElementById('txt').addEventListener('input', init);

init();
Result
Console

Notice the asymmetry: the failure function is computed once from the pattern in O(m)O(m) time. The search then scans the text left to right in O(n)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.

The Real Complexity

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

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

  • Naive search uses O(n×m)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)O(m) time and O(m)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)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)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":

index 0 1 2 3 4
char A B A B C
f[ ] 0 0 1 2 0

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.

Where It Matters

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×m)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).

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/kmp/Content licensed under CC BY-NC 4.0.