String Matching (KMP)

Efficient pattern matching in strings

KMP Algorithm

The Knuth-Morris-Pratt algorithm finds all occurrences of a pattern in a text in O(n + m) time by precomputing a failure function that avoids unnecessary comparisons.

typescript

// KMP Implementation
function kmpSearch(text: string, pattern: string): number[] {
  const lps = buildLPS(pattern);
  const result: number[] = [];
  let i = 0, j = 0;
  
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++; j++;
      if (j === pattern.length) {
        result.push(i - j);
        j = lps[j - 1];
      }
    } else {
      if (j > 0) j = lps[j - 1];
      else i++;
    }
  }
  return result;
}

function buildLPS(pattern: string): number[] {
  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;
}