# Find the starting indices of all occurrences of the pattern in the string [closed]

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

function findStartingIndex(T, pattern) {
let S = T;
const res = [];
while(true) {
const i = S.indexOf(pattern);
if (i === -1) { return res; }

S = S.substring(i + 1);
res.push(i ? i + 1 : i);
}
return res;
}

• a challenge like this is much more instructive if you don't use indexOf. See also: Knuth-Morris-Pratt – Oh My Goodness May 31 '19 at 1:32
• @OhMyGoodness thanks, just skimmed through the article but it sounds interesting. Will reimplement the code – thadeuszlay May 31 '19 at 1:35
• Your code does not work for many inputs. – Blindman67 May 31 '19 at 11:21
• @Blindman67 yes, I didn't test it thoroughly. Just pushed the code. :( I wish I could delete this. – thadeuszlay May 31 '19 at 11:35

For banana and a, it should return [1, 3, 5], but it doesn't.

Like @Roland Illig said, your code has bug with "banana" because of you mutable your string length each time you use your substring function.

I think you better replace your pattern each time it matchs by string that has same length pattern but does not match your pattern

function findStartingIndex(T, pattern) {
let S = T;
const res = [];
while(true) {
const i = S.indexOf(pattern);
if (i === -1) { return res; }
const newPattern = pattern.replace(/./,'_');

S = S.replace(pattern, newPattern);
res.push(i);
}
return res;
}



For string "banana" it will return [1,3,5]

Or you can consider my solution:

findStartingIndex = (s) => {
const result = [];
while (s.match(/abr/)) {
result.push(s.match(/abr/).index);
s=s.replace('abr','___');
}
return result;
}


Use regex here is not necessary but it is more flexible in case the pattern is dynamic.

Because I'm a fan of functional programming, I want to implement this without any for or while loops, which necessarily require mutating variables.

The way I'd do this, is with a recursive function.

function findIndexes(n, h, acc = [], currentIndex = 0) {
const index = h.indexOf(n);

if (index < 0) {
return acc;
} else {

const newHaystack = h.slice(index + 1);
return findIndexes(n, newHaystack, [...acc, index + currentIndex], currentIndex + index + 1);
}
}

console.log(findIndexes("a", "banana"));
Now, whether you want to implement that indexOf function yourself is up to you, but in any case - this how I'd do the rest of it.