Knuth-Morris-Pratt (KMP)

KMP (Knuth-Morris-Pratt) fixes the naïve method's core waste: after a partial match fails, the naïve search throws away everything it learned and re-reads the text. KMP refuses to. Before searching, it builds a small prefix table (the *lps* array, also called the failure function) straight from the pattern, and uses it to jump the pattern forward on a mismatch *without* moving the text pointer backward. The text is scanned exactly once.

What the prefix table stores

For each pattern position, lps[i] is the length of the longest proper prefix of the pattern (ending at i) that is also a suffix ending there. A *proper* prefix excludes the whole string itself. Intuitively: when a match breaks at position i, the matched part pattern[0..i-1] is known, and lps[i-1] tells you the longest already-matched chunk you can keep instead of restarting at zero.

Building lps for ABABAC

Walk the pattern, tracking the current matched prefix length len. When pattern[i] extends the prefix, len grows; when it breaks, fall back to lps[len-1] and try again.

index :  0  1  2  3  4  5
char  :  A  B  A  B  A  C
lps   :  0  0  1  2  3  0

lps[2]=1: prefix "A" reappears as a suffix of "ABA"
lps[4]=3: prefix "ABA" reappears as a suffix of "ABABA"
lps[5]=0: nothing of "ABABAC" ending in C starts the pattern

function buildLps(p) {
  const lps = new Array(p.length).fill(0);
  let len = 0;
  for (let i = 1; i < p.length; ) {
    if (p[i] === p[len]) lps[i++] = ++len;     // extend the prefix
    else if (len > 0) len = lps[len - 1];      // fall back, retry
    else lps[i++] = 0;                         // no prefix here
  }
  return lps;
}

Searching with it

1. 1Walk the text with pointer i; track how much of the pattern matches with j.
2. 2If text[i] === pattern[j], advance both i and j.
3. 3If j reaches the pattern length → a hit; set j = lps[j-1] to keep scanning for more.
4. 4On a mismatch with j > 0, set j = lps[j-1] — jump the pattern forward, leave `i` put.
5. 5On a mismatch with j == 0, just advance i.