KMP String Matching Pattern

When to use KMP String Matching

• You need to find every occurrence of a pattern P inside a text T and naive O(n * m) substring search is too slow.
• The problem asks 'is X a substring of Y' or 'how many times does X appear in Y' where both can be large.
• You need to compute the longest proper prefix that is also a suffix (LPS / failure function) of a string — this shows up in palindrome and rotation problems too.
• Rolling hash (Rabin-Karp) is unacceptable because the problem forbids randomized collisions or requires deterministic correctness.
• Problems involve string rotation, repeated patterns, or shortest palindrome construction where the LPS array gives the answer directly.

Template

function computeLPS(pattern) {
  const m = pattern.length;
  const lps = new Array(m).fill(0);
  let length = 0;
  let i = 1;
  while (i < m) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length > 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }
  return lps;
}
function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [0];
  const lps = computeLPS(pattern);
  const matches = [];
  let i = 0;
  let 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 (j > 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }
  return matches;
}

Common mistakes

• Resetting length to 0 on every mismatch in the LPS build instead of falling back to lps[length - 1], which destroys the O(m) build complexity and may even compute a wrong table.
• Backing up the text pointer i after a mismatch — KMP's whole point is that i only ever moves forward; backing up turns it into naive search.
• Confusing 'longest prefix that is also a suffix' with 'longest border' and including the full string itself, producing an LPS array that is too long by one.
• Returning from the search after the first match when the problem actually wants all matches — remember to set j = lps[j - 1] and continue scanning instead of returning early.
• Failing to handle the empty-pattern edge case, which under naive semantics matches at every position including length n + 1; pick a convention up front and stick with it.