jsschools

KMP (Knuth-Morris-Pratt) Algorithm

Finds all occurrences of a pattern in a text in O(n + m) by precomputing a failure function that avoids redundant character comparisons on mismatch.

Spec ↗

Syntax

kmpSearch(text, pattern)

Parameters

NameTypeRequiredDescription
text string Yes The string to search within (length n).
pattern string Yes The pattern to search for (length m). Must be non-empty.

Returns

number[] — Array of starting indices (0-based) where pattern occurs in text.

Examples

function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0, i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) { lps[i++] = ++len; }
    else if (len > 0) { len = lps[len - 1]; }
    else { lps[i++] = 0; }
  }
  return lps;
}

function kmpSearch(text, pattern) {
  const lps = buildLPS(pattern);
  const matches = [];
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) { i++; j++; }
    if (j === pattern.length) { matches.push(i - j); j = lps[j - 1]; }
    else if (i < text.length && text[i] !== pattern[j]) {
      if (j > 0) j = lps[j - 1]; else i++;
    }
  }
  return matches;
}

console.log(kmpSearch('AABAACAADAABAABA', 'AABA'));
Output 
[ 0, 9, 12 ]

// Pattern not found
function buildLPS(p) {
  const lps=new Array(p.length).fill(0); let len=0,i=1;
  while(i<p.length){ if(p[i]===p[len]){lps[i++]=++len;}else if(len>0){len=lps[len-1];}else{lps[i++]=0;} } return lps;
}
function kmpSearch(text, pattern) {
  const lps=buildLPS(pattern); const matches=[]; let i=0,j=0;
  while(i<text.length){ if(text[i]===pattern[j]){i++;j++;} if(j===pattern.length){matches.push(i-j);j=lps[j-1];} else if(i<text.length&&text[i]!==pattern[j]){if(j>0)j=lps[j-1];else i++;} }
  return matches;
}

console.log(kmpSearch('hello world', 'xyz'));
Output 
[]

Notes

| Case | Time | Space | |---------|-----------|-------| | Best | O(n + m) | O(m) | | Average | O(n + m) | O(m) | | Worst | O(n + m) | O(m) | The failure function (LPS — Longest Proper Prefix which is also Suffix) is the key insight: on a mismatch at position j, instead of resetting j = 0, we jump to j = lps[j-1] — reusing the work already done. This guarantees the text pointer i never moves backward. KMP is preferred over the naïve O(nm) approach for large texts or repeated queries. For multiple patterns, Aho-Corasick generalises KMP with a trie.

See also