string-search • Advanced

Knuth-Morris-Pratt (KMP) String Pattern Matching & LPS Array

KMP eliminates backtracking in naive string matching (O(N * M)) down to linear O(N + M) by precomputing the Longest Prefix Suffix (LPS) table to skip redundant character comparisons.

Intuitive Mental Model

The Bookmark in the Book: When encountering a typo at letter 6 of a word, you do not flip back to page 1; your bookmark tells you exactly which prefix letters you already matched.

C / TypeScript ImplementationHardware & Algorithmic Standard

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let 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;
}

Key Architectural Takeaways

•LPS[i]: Stores the length of the longest proper prefix of pattern[0..i] that is also a suffix.
•Zero Backtracking: The text index pointer i NEVER moves backward, ensuring linear O(N) execution time.

Common Coding Mistake

Resetting the pattern index to 0 upon mismatch instead of using lps[j - 1].

Optimal Solution

Always transition to j = lps[j - 1] on mismatch when j > 0.

Next: Rabin-Karp Rolling Hash & Modular String Matching