KMP Algorithm

KMP (Knuth-Morris-Pratt) is a string pattern matching algorithm that finds all occurrences of a pattern within a text efficiently.

function buildLPS(pattern) {
  const n = pattern.length;
  const lps = new Array(n).fill(0);
  let len = 0;
  let i = 1;

  while (i < n) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

function kmpSearch(text, pattern) {
  if (pattern.length === 0) return [];

  const n = text.length;
  const m = pattern.length;
  const results = [];

  const lps = buildLPS(pattern);

  let i = 0;  // pointer for text
  let j = 0;  // pointer for pattern

  while (i < n) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }
    

if (j === m) {
  results.push(i - j);
  j = lps[j - 1];
} else if (i < n && text[i] !== pattern[j]) {
  if (j !== 0) {
    j = lps[j - 1];
  } else {
    i++;
  }
}

  }

  return results;
}

Build LPS

LPS (Longest Prefix-Suffix) represents the length of the longest proper prefix of the substring pattern[0..i] that is also a suffix of that substring.

function buildLPS(pattern) {
  // pattern length
  const n = pattern.length;
  // initiate lps array filled with 0
  const lps = new Array(n).fill(0);
  // initiate len. len represents both the count of matched characters and the index we compare against
  let len = 0;
  // initiate pointer starting from 1. i represents we are dealing with pattern[0..i]
  let i = 1;

  while (i < n) {
    // if i pointer equals to len, push len forward, align len to lps[i] and move forward to compare next 			 character
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } 
    // when not matches
    else {
      // if len is greater than 0, align lps[len-1] to len ①
      if (len !== 0) {
        len = lps[len - 1];
      } 
      // if len is 0, it means there is no proper prefix of pattern[0..i] that is also a suffix
      // between pattern[0..i]. So align 0 to lps[i] 
      // and we move forward to next character
      else {
        lps[i] = 0;
        i++;
      }
    }
  }
  // after processed all characters in pattern, return lps array
  return lps;
}

YOU MAY ASK

① Why len = lps[len - 1]? Why not len = 0? Practically, for pattern AABAAA, at i = 5 if use len = 0, lps[5] would be 0 instead of 2. Theoretically, if pattern[i] !== pattern[len], the current prefix of length len no longer works. But here’s the insight: Maybe a shorter prefix inside that pattern[0..len-1] is still a suffix that matches. That shorter prefix’s length is already stored in lps[len - 1]. So we try: len = lps[len - 1], That’s the next best candidate prefix that could still align with the current suffix. For example, for ABABAC, they mismatch when comparing 6th with 4th , the len jump to 2nd instead of trying 3rd.

KMP Search Function

function kmpSearch(text, pattern) {
  // return if the pattern length is 0
  if (pattern.length === 0) return [];
  // initiate n representing text length
  const n = text.length;
  // initiate m representing pattern length
  const m = pattern.length;
  // initiate results array which store all occurrences of the pattern within the text 
  const results = [];

  // build lps using the algorithm we introduced above
  const lps = buildLPS(pattern);

  // initiate two pointers
  let i = 0;  // pointer for text
  let j = 0;  // pointer for pattern


  while (i < n) {
    // move two pointers forward if the corresponding character matches
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }

	// if j reaches to m, it means the pattern is fully matched,
	// we push the start position(i-m) to results array and we align j ①
	if (j === m) {
		results.push(i - m);
 		j = lps[j - 1];
	} 
	// if i still smaller than n and the corresponding character doesn't matches
	else if (i < n && text[i] !== pattern[j]) {
 		 // and if j doesn't equal to 0, we gonna check the next best candidate prefix that could still align 		with the current suffix. So we ②
 	 if (j !== 0) {
  		j = lps[j - 1];
 	 } 
  	// otherwise, j already equals to 0, it means this character doesn't match any character in pattern
  	// so we move forward to check next character in the text
 	 else {
  	 		i++;
 	 }
	}
}

  return results;
}

① Let's say m = pattern.length and Lps[m] = k (k is some value in lps array).

Definition of lps:

pattern[0...k-1] == pattern[m-k...m-1]. In other words: prefix of length k == suffix of length k.

Given:

pattern[0...m-1] == text[i-m...i-1] ← (full match we just made).

pattern[0...k-1] == pattern[m-k...m-1] ← (from lps definition).

pattern[m-k...m-1] == text[i-k...i-1] ← (last k chars of matched text).

Therefore:
pattern[0...k-1] == text[i-k...i-1], the prefix of the pattern match the i-k to i-1 of the text. Thus we DON'T need to re-compare pattern[0...k-1] with text[i-k...i-1]. Instead, we can jump to: Check pattern[k] vs text[i], so we need to set pointer j to k, the k value is exactly in lps array. So why specifically j-1, cuz it's "in sync" with what came before, so it's more likely to match what comes next. (this 'more likely' does not mean random guessing, but we're trying systematically valid positions based on the pattern's structure). So we need to fallback one by one from the best candidate.

This is an example:

The pattern might overlap with itself. After matching "ABAB" at the start:
● If we just reset j = 0, we’d recheck from scratch. ● But notice the suffix "AB" of the match is also a prefix of the pattern. ● That’s stored in lps[j - 1] = 2. So we continue from that prefix (reusing overlap).

② This is more like we met in building lps, text[i] !== pattern[j] means the current prefix of length j no longer works. But here’s the insight: Maybe a shorter prefix inside that pattern[0..j-1] is still a suffix that matches. That shorter prefix’s length is already stored in lps[j - 1]. So we try: len = lps[j - 1], That’s the next best candidate prefix that could still align with the current suffix.

Conclusion: These 2 are the same code, but represents different meaning and lead j pointer to different position. This is an example:

when i == 4 j == 4, j jump to lps[2] which is 0; but when i reaches 5 and j == 2 at the same time, j fallbacks to 1;

What else we can take away from LPS array?

Given a string, if n % (n - LPS[n-1]) == 0, then the string is made of repeating pattern. and the pattern length is n - LPS[n-1].

Why?

If the string can be made by a repeated substring, then n % pattern.length === 0. So the question becomes what is pattern.length. We can't know it directly, but we can get LPS array through KMP algorithm, so the problem is how to get pattern.length through LPS. Let's assume the string is repeated string, so here are two truths about it:

1. n = k x p, k is a number and p is the length of the substring. This means the string length is made by k pattern.length. It's easy to understand.
2. Maximum matching prefix/suffix = LPS[n-1] = (k-1) × p, . we need a proper prefix/suffix (meaning NOT the entire string), so the longest matching prefix/suffix is n - pattern.length, the string length minus ONE pattern.

We can calculate from these two truths: LPS[n-1] = n - p ==> p = n - LPS[n-1] Now we know the pattern.length. So if n % (n - LPS[n-1]) === 0, it means n % pattern.length === 0 , which means the string is made by a repeated substring.

(Leetcode 459)