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

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;
}

• Did you write automated tests? Which are your test cases? As you saw in the previous question, a single test case is not enough. If you only had this single test case, the expression (() => [0, 7]) would satisfy all test cases, even though it is clearly wrong. May 31, 2019 at 22:32
• @RolandIllig Nope, I didn't write automated tests. But maybe I should in the future. I only tested some cases that I thought were critical: abracadabra | abr, banana | a, 12121212 | 1212, 1111 | 1 May 31, 2019 at 22:39

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,7]",JSON.stringify(findStartingIndexes("abracadabra","abr")));