↩ back to Exact Match

Knuth-Morris-Pratt (KMP) String Matching

Finding one string inside another sounds trivial: slide the pattern along the text one position at a time, and at each position compare characters until either the whole pattern matches or one character doesn't. That's naive search, and it's correct — but a mismatch throws away everything the comparison just learned and restarts the pattern from its first character at the very next position, even when the text just spent several characters proving part of the pattern does show up there. On most everyday inputs that barely matters. On repetitive ones it's genuinely quadratic: searching for AAAAAAAAAB (nine As then a B) inside AAAAAAAAAAAAAAAAAAAB (nineteen As then a B) — the demo's own default input — takes naive search 110 character comparisons (checked below, not just claimed). The Knuth-Morris-Pratt (KMP) algorithm solves the identical search in 30. It never re-examines a text character more than a bounded number of times, by precomputing, once, a small table that says exactly how much of a partial match can be reused after a mismatch instead of rebuilt from scratch.

Try it

Enter a text to search and a pattern to find inside it (up to 30 and 12 characters). Step through two phases: first, building the LPS table ("longest proper prefix that's also a suffix") by comparing the pattern against itself — no text involved yet; then searching, sliding the pattern's actual current alignment under the text and consulting that table every time a comparison fails instead of restarting from the pattern's first character. Matched runs turn green, a failed comparison flashes, and the running comparison count is shown next to what naive search would have needed for the exact same input.

Why it works

The LPS table has one entry per pattern position: lps[i] is the length of the longest proper prefix of pattern[0..i] (not the whole thing) that is also a suffix of it. Building it compares the pattern against itself with two pointers, i walking forward and len tracking the current matched prefix length: when pattern[i] extends the match, len grows and lps[i] = len; when it doesn't and len is already 0, lps[i] = 0 and move on; when it doesn't but len > 0, fall back to len = lps[len - 1] and try again without advancing i — the same "don't discard everything, reuse what's already known" idea the search phase reuses next.

The search keeps an invariant: whenever it's partway through comparing at text index i and pattern index j, the j characters just before i in the text are known to equal pattern[0..j-1] — that's exactly what made it this far. So when text[i] and pattern[j] disagree, the search already knows the last j text characters; the question is only how much of the pattern's own prefix could still line up against the end of that known-matched run. That is precisely what lps[j-1] answers — the longest proper prefix of the pattern that is also a suffix of what's already matched — so jumping the pattern pointer straight to j = lps[j-1] (instead of back to 0) skips only comparisons that are guaranteed to succeed anyway, never a comparison that might have found something. The text index i never moves backward at all; only the pattern's alignment slides.

Reference implementation

This is the exact scheme the demo above steps through, split into the two phases:

function computeLPS(pat) {
  const m = pat.length;
  const lps = new Array(m).fill(0);
  let len = 0, i = 1;
  while (i < m) {
    if (pat[i] === pat[len]) {
      len++;
      lps[i] = len;
      i++;
    } else if (len !== 0) {
      len = lps[len - 1];          // fall back, i stays put
    } else {
      lps[i] = 0;
      i++;
    }
  }
  return lps;
}

function kmpSearch(text, pat) {
  const lps = computeLPS(pat);
  const n = text.length, m = pat.length;
  const matches = [];
  let i = 0, j = 0;
  while (i < n) {
    if (text[i] === pat[j]) {
      i++; j++;
      if (j === m) {
        matches.push(i - j);       // found — record start index
        j = lps[j - 1];            // keep scanning for overlaps
      }
    } else if (j !== 0) {
      j = lps[j - 1];              // fall back, text index stays put
    } else {
      i++;                         // no match to fall back on — advance text
    }
  }
  return matches;
}

Pitfalls

The fallback after a full match has to reuse lps, not reset to zero — and the difference is invisible until the match overlaps itself. A tempting "simplification" sets j = 0 once j === m, on the reasoning that a match was just found so the search should obviously start clean. It's wrong, and it fails silently rather than crashing: searching for AA in AAAA, the correct fallback (j = lps[j-1] = lps[1] = 1) finds all three overlapping occurrences, [0, 1, 2]; the j = 0 variant finds only [0, 2], silently dropping the match at index 1 because it threw away the one already-matched character (the second A) that the correct version knew it could reuse. Checked against a brute-force scan of every start index, not just eyeballed. This is exactly the same "keep, don't discard, what's already proven" idea the Why-it-works section above depends on — get it wrong in the one place it's easy to get wrong (right after a match, not mid-match) and matches quietly go missing instead of the algorithm erroring out.

The quadratic worst case is real, but it needs a repetitive pattern to show up. The 110 vs 30 comparison gap in this page's intro isn't a hand-picked fluke — it's what a long run of one repeated character followed by a near-miss forces on naive search, because every one of the pattern's near-matches at every offset gets re-walked almost to completion before failing. Search a pattern with no internal repetition (every character distinct) against ordinary text, though, and naive search is usually close to linear in practice — most mismatches happen on the very first character compared at each position, so there's rarely much partial work to redo. KMP's guarantee is worst-case O(n+m) unconditionally; its actual speedup over naive search on any specific input depends entirely on how repetitive the pattern is, which is exactly why the LPS table for a repetition-free pattern is all zeros (there's no proper prefix-that's-also-a-suffix to find) and the search degenerates to behaving like naive search anyway, just with a small table-lookup on top.

KMP finds one pattern. Searching a text for many patterns at once is a different, harder problem. Running KMP once per pattern against the same text works, but costs O(k·(n+m)) for k patterns — the text gets rescanned from scratch every time. Aho-Corasick generalizes the exact same failure-link idea to a trie holding every pattern at once, so the whole text is scanned a single time regardless of how many patterns are being matched simultaneously.

KMP finds a match by comparing characters, just smarter about which ones it re-examines. A completely different approach exists: compare cheap numeric fingerprints of the pattern and each text window instead of comparing characters at all, and only fall back to characters when two fingerprints happen to agree. Rabin-Karp does exactly that — it trades KMP's unconditional O(n+m) worst-case guarantee for a usually-faster average case, at the cost of needing to verify every fingerprint match before trusting it. A third approach keeps comparing characters but changes which direction: Boyer-Moore compares the pattern against the text right to left, so a single mismatch on the pattern's last character can rule out large stretches of text at once — often the fastest of the three in practice, at the cost of KMP's own unconditional worst-case guarantee.

Complexity

Time: O(m) to build the LPS table, then O(n) to search — O(n+m) total, and that bound holds for every input, not just typical ones. The search-phase argument: the text index i only ever moves forward, so it advances at most n times total across the whole run; the pattern index j only ever increases alongside i or strictly decreases on a fallback (and it can't go below where it's been before without i having advanced to get it there), so the total number of fallback steps is bounded by the total number of times j was able to increase, which is itself bounded by n. Neither pointer does extra backtracking work beyond that bound — unlike naive search, which can redo up to m comparisons at every single one of the n starting positions. Space: O(m) for the LPS table, O(1) beyond that (excluding the list of match positions returned) — the text itself is never copied or modified, only scanned once left to right.

Every algorithm above compares the pattern against the text directly, at search time. Suffix Array takes a different approach again: sort the text's own suffixes once, up front, and answer any pattern decided later — one nobody knew about when the text was indexed — with a pair of binary searches instead of a fresh scan. See Choosing an Exact-Match String Matcher for how this guarantee compares to the other nine exact-match entries.