Knuth-Morris-Pratt

The 10-second versionCopy Anchor Link

Knuth-Morris-Pratt (KMP) finds a pattern of length m inside a text of length n in O(n + m) time. The trick is a precomputed array — the failure function or prefix function — that records, for every prefix of the pattern, the length of the longest proper prefix that is also a suffix. When a mismatch happens, instead of jerking the pattern backwards and re-checking characters you already know match, you consult that array and slide the pattern forward just enough. The text pointer never moves backwards, and that is the entire reason it's linear.

Why this existedCopy Anchor Link

The obvious way to search for a pattern is to try every starting position: line the pattern up, compare characters left to right, and when they disagree, shift the pattern over by one and start again. Correct, and agonizingly slow in the worst case — O(n × m). Feed it a text like aaaaaa...a and a pattern like aaaaab, and you'll re-compare almost everything over and over. On the hardware of the 1960s and 70s, that cost was real: compilers, text editors, and information-retrieval systems all searched constantly.

Three people, working separately, arrived at the same fix within a couple of years:

• 1970 — Donald Knuth and Vaughan Pratt derive a linear-time matcher, and it circulates as a technical report.
• 1970 — James Morris, while building a text editor, independently invents the same idea — sometimes called Morris-Pratt in early write-ups.
• 1977 — the three combine their results into one landmark paper, "Fast Pattern Matching in Strings," in the SIAM Journal on Computing. The credits are shared and the algorithm gets its famous hyphenated name.

Why it mattered then: searching was a bottleneck in the tools that people used every day. A guaranteed linear bound — no adversarial input could blow it up — turned string search from "fast enough for small inputs" into "fast enough for anything."

Inside the inventor's headCopy Anchor Link

Watch the naive matcher waste work. Text abababab, pattern ababc:

That last line is the whole insight. After matching a b a b and failing on the next character, the naive algorithm throws away the knowledge that a b a b matched. But a b — a prefix of the pattern — is also a suffix of that matched piece. So we can slide the pattern to line that overlap up and continue, keeping every character of the text we've already looked at.

The first attempt people make is "shift by the length of the overlap," which is right in spirit — but you need that overlap length for every position, not just the whole matched run, because a mismatch can happen after any amount of progress. So Knuth, Pratt and Morris precompute it into a table: for each index i, π[i] is the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. That's the failure function.

Contrast the wasted work with the fixed version:

// Naive: on mismatch, restart the pattern at the next text position — O(nm)function naiveFind(t, p) {  for (let i = 0; i + p.length <= t.length; i++) {    let j = 0;    while (j < p.length && t[i + j] === p[j]) j++;    if (j === p.length) return i;  }  return -1;}// KMP: on mismatch, fall back to the longest known overlap — never recheck// t[i] === p[k] ? then k++ : k = pi[k - 1] (and only the pattern moves back)

The final approachCopy Anchor Link

The prefix functionCopy Anchor Link

For pattern P, define π[i] as the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. ("Proper" means shorter than the whole thing — the empty prefix always counts, so π[0] = 0.)

For P = a b a b c:

So π = [0, 0, 1, 2, 0].

The search walkCopy Anchor Link

The π array itself is built with the same loop, searching the pattern in itself.

The invariantsCopy Anchor Link

1. Match state. Just before text character i, we have matched the first k characters of the pattern against the k characters of the text ending at i - 1. k is the longest such match ending there.
2. Fall-back correctness. On mismatch, k = π[k - 1] gives the next-longest overlap length, so the pattern shifts to the only position that can still match. No candidate position is skipped, and no text character is re-examined.
3. No backtracking. The text index i only ever moves forward. This single fact is what guarantees linear time.

The amortized "why is it linear?"Copy Anchor Link

Here's the argument that makes people nod. Let k be the number of pattern characters currently matched.

• k increases by at most 1 per text character — there are only n characters, so the total increase over the whole search is at most n.
• Every fall back strictly decreases k, and k is never negative, so the total decrease can never exceed the total increase.
• Therefore the while loop that falls back runs at most n times in total, not n times per text character.

So the mismatch handling, which looks like it could be O(n) each time, is O(n) once, amortized. Preprocessing costs O(m), searching costs O(n), total O(n + m).

A worked traceCopy Anchor Link

P = a b a b c (so π = [0, 0, 1, 2, 0]), T = a b a b a b c:

Notice at i=4 we did not move back in the text. We slid the pattern from offset 0 to offset 2 by reading π, and carried the knowledge that a b already matched.

It in codeCopy Anchor Link

// pi[i] = length of the longest proper prefix of p[0..i] that is also a suffixfunction buildPi(p) {  const pi = new Array(p.length).fill(0);  let k = 0;  for (let i = 1; i < p.length; i++) {    while (k > 0 && p[i] !== p[k]) k = pi[k - 1];    if (p[i] === p[k]) k++;    pi[i] = k;  }  return pi;}// returns the index of the first occurrence of p in t, or -1function kmpFind(t, p) {  const m = p.length;  if (m === 0) return 0;  const pi = buildPi(p);  let k = 0;  for (let i = 0; i < t.length; i++) {    while (k > 0 && t[i] !== p[k]) k = pi[k - 1];    if (t[i] === p[k]) k++;    if (k === m) return i - m + 1;  }  return -1;}

ComplexityCopy Anchor Link

Unlike naive search, there is no bad input — aaaaa… and abcabc… all run in linear time.

Finding every matchCopy Anchor Link

Because k = m means a full match, you can fall back to π[m - 1] and keep scanning to report all occurrences in one pass:

function kmpFindAll(t, p) {  const m = p.length;  const pi = buildPi(p);  const hits = [];  let k = 0;  for (let i = 0; i < t.length; i++) {    while (k > 0 && t[i] !== p[k]) k = pi[k - 1];    if (t[i] === p[k]) k++;    if (k === m) {      hits.push(i - m + 1);        // keep going — there may be overlaps      k = pi[k - 1];    }  }  return hits;}

Where you meet it todayCopy Anchor Link

• Language runtimes. Functions like strstr, indexOf, and the search inside many grep implementations carry KMP's DNA — linear search with no pathological blowups.
• Text editors and diff tools. Finding and re-finding patterns as a document changes is exactly the incremental search KMP was born from.
• Bioinformatics. Scanning a genome for a motif is pattern matching over millions of characters; the guaranteed linear bound matters more than any constant factor.
• Multi-pattern search. Aho-Corasick builds on the same failure-function idea to search for many patterns at once — the engine behind network intrusion detection and keyword scanners.

// b is a rotation of a  iff  b occurs inside a + aconst isRotation = (a, b) =>  a.length === b.length && kmpFind(a + a, b) !== -1;

RecapCopy Anchor Link

• KMP searches in O(n + m) by never moving the text pointer backwards — no input can make it quadratic.
• The prefix function π[i] records the longest proper prefix of P[0..i] that is also a suffix, and it is what drives the fall-back on a mismatch.
• The linear bound is amortized: k rises by at most one per text character and every fall back lowers it, so all fall backs together cost O(n).
• The same loop builds π and searches the text; falling back from a full match finds every overlapping occurrence in one pass.

Next up: Rabin-Karp & Rolling Hash — a randomized alternative that trades KMP's careful bookkeeping for a single arithmetic trick.