Find the starting indices of all occurrences of the pattern in the string - KMP algorithm follow-up

Question

The task

was initially solved here, but was too buggy:

Given a string and a pattern, find the starting indices of all occurrences of the pattern in the string. For example, given the string "abracadabra" and the pattern "abr", you should return [0, 7].

My solution

Tried to solve it using KMP-algorithm:

function findStartingIndex(T, pattern) {
  if (pattern.length > T.length) { return []; }

  let next = 0;
  const res = [];

  const check = i => {
    for (let j = 1; j < pattern.length; j++) {
      if (next <= i && T[i + j] === pattern[0]) { next = i + j - 1; }
      if (T[i + j] !== pattern[j]) { return false; }
    }
    if (next <= i) { next = i + pattern.length - 1; }
    return true;
  };

  for (let i = 0; i < T.length; i++) {
    if (i + pattern.length > T.length) { return res; }
    if (T[i] === pattern[0] && check(i)) { res.push(i); }
    i = next;
  }
  return res;
}

Answer 1

A quick review;

• This tends to find more than 1 index, findStartingIndex -> findStartingIndexes
• In KMP, T is a lookup table, not the source string
• If you used the while statement proposed by Wikipedia, you would not need the first if statement
• In KMP, they use a lookup table, your code does not
• You have a tendency to one line if statements, it hampers readability
• Your code does not actually work findStartingIndex("abracadabra","abr") goes into an infinite loop, next doesn't get updated, and so keeps getting reset to 2
• I wrote a counter proposal, it does use a bit of optimization but it does not use a search table like KMP, and is in my opinion far more understandable/readable

function findStartingIndexes(haystack, needle){
  
  const needleLength = needle.length;
  const searchSpace = haystack.length - needleLength;
  const indexes = [];
  let position = 0;
  
  while(position <= searchSpace){
    if(haystack[position] == needle[0] &&
      haystack.slice(position, position + needleLength) == needle) {
          indexes.push(position);
      }
    position++;
  }
  return indexes;
}

function findStartingIndex(T, pattern) {
  if (pattern.length > T.length) { return []; }

  let next = 0;
  const res = [];

  const check = i => {
    for (let j = 1; j < pattern.length; j++) {
      if (next <= i && T[i + j] === pattern[0]) { next = i + j - 1; }
      if (T[i + j] !== pattern[j]) { return false; }
    }
    if (next <= i) { next = i + pattern.length - 1; }
    return true;
  };

  for (let i = 0; i < T.length; i++) {
    if (i + pattern.length > T.length) { return res; }
    if (T[i] === pattern[0] && check(i)) { res.push(i); }
    i = next;
  }
  return res;
}

//Infinite loop ;(
//console.log("[0,2]",JSON.stringify(findStartingIndex("abracadabra","abr")));

console.log("[0,2]",JSON.stringify(findStartingIndexes("ababab","abab")));
console.log("[]", JSON.stringify(findStartingIndexes("","abab")));
console.log("[0,7]",JSON.stringify(findStartingIndexes("abracadabra","abr")));