KMP Pattern Matching

How it works, step by step

1. 1

   Before touching the text, study the pattern. Build the lps table: for each position, the length of the longest proper prefix of the pattern that is also a suffix of the part read so far.

2. 2

   That table answers one question: "I matched j characters and then failed - how many of them still count after sliding the pattern forward?"

3. 3

   Now scan. Text pointer i, pattern pointer j. When text[i] equals pattern[j], both move forward - this part is exactly like naive matching.

4. 4

   On a mismatch with j > 0, do not move i. Set j = lps[j - 1]: the pattern slides forward, the overlap is kept, and no text is re-read.

5. 5

   On a mismatch with j = 0, there is nothing to reuse - move i forward by one.

6. 6

   When j reaches the pattern length, a match starts at i - j. Set j = lps[j - 1] and keep scanning to find every occurrence, overlapping ones included. Total work: O(n + m).

The code, in JavaScript

function buildLps(pattern) {
  // lps[i] = length of the longest PROPER prefix of pattern.slice(0, i + 1)
  // that is also a suffix of it. "Proper" = shorter than the piece itself,
  // which is why lps[0] is always 0.
  const lps = new Array(pattern.length).fill(0);
  let len = 0;             // length of the current border (prefix = suffix)
  let i = 1;               // lps[0] is settled, start at 1

  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      // The border grows by one character.
      len++;
      lps[i] = len;
      i++;
    } else if (len > 0) {
      // The border cannot grow. Do NOT reset to zero:
      // a shorter border may still work - and lps already knows it.
      len = lps[len - 1];  // note: len - 1, not len
    } else {
      // No border at all ends here.
      lps[i] = 0;
      i++;
    }
  }
  return lps;
}

buildLps("ABABC");   // → [0, 0, 1, 2, 0]
buildLps("AAAA");    // → [0, 1, 2, 3]
buildLps("ABCDE");   // → [0, 0, 0, 0, 0]

Dry run: finding ABABC inside ABABABCABAB

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• The lps table is built from the pattern only. A surprisingly common bug is trying to build it from the text. The table is what the pattern knows about itself - the text is only ever read once, forward.
• "Proper" prefix means: not the whole string. That is why lps[0] is always 0. Allow the whole string and every lps[i] becomes i + 1 - the pattern never really slides, and the search can loop forever.
• On a mismatch you consult `lps[j - 1]`, not `lps[j]`. You are asking about the j characters that DID match, not the one that failed. This off-by-one often survives easy tests and then breaks on repetitive input.
• For one small search, KMP is often *slower* than naive - the table costs time and the constant factor is higher. It pays off on repeated searches, streams, and adversarial input. Know why you are reaching for it.

KMP Pattern Matching vs. its closest relatives