There are still two slight issues with this code. Can you see what they are?
Let's take the examples of a string ggraph
and substring graph
. On the first iteration, g
will match g
, which is what we want. However, on the next iteration, we will try to match the second g
in ggraph
with r
in graph
.
What should happen is if we don't find a match, we ought to reset i
a bit as well-- this is to accommodate duplicate characters. We can reset it specifically to the length of the last processed substring (or j
).
The other thing is regarding the index of the start of the match-- we can simply get it from i - (subStr.length - 1)
. Note that you need to subtract 1
from the substring's length in order to get to the correct index.
Complexity of Final Solution
Let n
be the length of the string. In the worst-case scenario, we iterate through all n
characters of the string and do not find a match. Many of us will then declare that the time complexity is linear O(n)
. But think carefully, for each partial matching of substrings, we are traversing through the substring, and then again resetting to the initial pointer i
.
To get a more clear insight into this, let's consider an example:
1str = "aaaaaa"
2subStr = "aab"
The final solution code of the method explained above is given.
xxxxxxxxxx
function detectSubstring(str, subStr) {
let idxOfStart = 0,
j = 0;
​
for (i = 0; i < str.length; i++) {
// if match, compare next character of subStr with next of string
if (str[i] == subStr[j]) {
j++;
if (j == subStr.length) {
return i - (subStr.length - 1);
}
} else {
i -= j;
j = 0;
}
}
​
return -1;
}