# 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. – Roland Illig May 31 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 – thadeuszlay May 31 at 22:39