Алгоритм Кнута-Морриса-Пратта (KMP) — Реализация функции strStr()

const allPointers = [];
var strStr = function (haystack, needle) {
  if (needle === "") return 0;
  const prefixTable = lpsTable(needle);
  let i = 0;
  let j = 0;
  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i += 1;
      j += 1;
    }
    if (j === needle.length) {
      allPointers.push(i - j);
      j = prefixTable[j - 1];
    } else if (i < haystack.length && haystack[i] !== needle[j]) {
      if (j > 0) {
        j = prefixTable[j - 1];
      } else {
        i += 1;
      }
    }
  }
};

console.log(allPointers);

var lpsTable = function(word){
const patternTable = [0];
    let prefixIndex = 0;
    let suffixIndex = 1;

    while (suffixIndex < word.length) {
      if (word[prefixIndex] === word[suffixIndex]) {
        patternTable[suffixIndex] = prefixIndex + 1;
        suffixIndex += 1;
        prefixIndex += 1;
      } else if (prefixIndex === 0) {
        patternTable[suffixIndex] = 0;
        suffixIndex += 1;
      } else {
        prefixIndex = patternTable[prefixIndex - 1];
      }
    }

    return patternTable;
}