I was doing a little studying on algorithms when I stumbled into what looked to me as a pretty simple question: “Find the first occurrence of a string inside another string”. This can be simply achieved with two nested loops and a worst case scenario performance of O(nm) or O(n^2) if m’s size is relative to n.

Here is an implementation that uses two loops:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | function findString(s1, s2) { // We only need to loop until s2 doesn't fit anymore var loopLimit = s1.length - s2.length; for (var i = 0; i < = loopLimit; i++) { for (var j = 0; j < s2.length; j++) { // As soon as we find a mismatch we abort the loop if (s1[i + j] !== s2[j]) { break; } } // If j reached the size of s2, it means all letters // in s2 matched. We have succeeded! if (j === s2.length) { return true; } } return false; } findString('aaaaaaaaaa', 'aaaab'); // false findString('aaaaaaaaab', 'aaaab'); // true findString('aaaaaaaaab', 'ab'); // true |