Knuth-Morris-Pratt (KMP) Algorithm

1function computeLPSArray(pattern) {
2  const lps = new Array(pattern.length).fill(0);
3  let len = 0; // Length of previous longest prefix suffix
4  let i = 1;
5 
6  while (i < pattern.length) {
7    if (pattern[i] === pattern[len]) {
8      len++;
9      lps[i] = len;
10      i++;
11    } else {
12      if (len !== 0) {
13        len = lps[len - 1]; // Fallback to previous longest prefix
14      } else {
15        lps[i] = 0;
16        i++;
17      }
18    }
19  }
20  return lps;
21}
22 
23function kmpSearch(text, pattern) {
24  if (!pattern || !text || pattern.length > text.length) return [];
25 
26  const lps = computeLPSArray(pattern);
27  const matches = [];
28  let i = 0; // index pointer for text
29  let j = 0; // index pointer for pattern
30 
31  while (i < text.length) {
32    if (pattern[j] === text[i]) {
33      i++;
34      j++;
35    }
36 
37    if (j === pattern.length) {
38      matches.push(i - j); // Found match starting at index (i - j)
39      j = lps[j - 1]; // Check for overlapping matches
40    } else if (i < text.length && pattern[j] !== text[i]) {
41      if (j !== 0) {
42        j = lps[j - 1]; // Shift pattern using LPS without rewinding i
43      } else {
44        i++;
45      }
46    }
47  }
48 
49  return matches;
50}
51 
52// Example usage:
53// kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"); // Returns [10]