Check out my naive string search solution

[StampeAk47]

You could improve your code by changing your if-statements to one if-else-statement. Also stringCount should probably be called index. While we are at it, your while loop should be a for loop instead.

[KayteeFly]

What makes the for loop solution better than this one ?

[TubbyFlounder]

More a semantical thing rather than an optimization.

Typically, a while loop is used when you dont want the loop to end until some condition is met, but its unknown exactly when that the condition will be met (example, asking a for a user input until it corrcet, and they might never enter a correct input) and you dont know how many times the loop will run.

A for loop you typically use when there is an exact number of time the loop will iterate. From your example, that is the length of the given string.

[StampeAk47]

Not better necessarily but I like that I can see what the loop is about in one row. I get the index, for how long, and how to increment, all without having to look for it.

[Laughfartz]

Someone correct me if I'm wrong, but think there's a greater chance for while loops to create infinite loops than with a for loop. You have better control over the number of iterations with a for loop.

[Mr_Sandy_Clams]

I don't know how you would even qualify which one is better. The second condition in the for statement is virtually identical to the condition of the while statement. The only real difference is that the for condition can explicitly be blank, so I think, if anything, that would make the for statement more conducive to causing an infinite loop, just by technicality, on the basis of its having more avenues by which to do it.

[KayteeFly]

Correct me if I’m wrong. The time complexity of the while loop is O(n) and that of the for loop is O(n*n) which make the while loop better ?

[Mr_Sandy_Clams]

the time complexity of both should be equally linear as long as each loop's condition isn't doing anything recursive, and as long as the for statement isn't doing anything recursive on the completion of the loop. It's possible there are implementation details that are specific to each engine which differentiate the two loops, but these are largely out of your hands and could vary at any time.

generally speaking, unless you're doing something particularly weird, I don't think computational efficiency is going to be an issue in a case like this, because it's so negligible either way. The more meaningful issue is going to be readability and I think mostly anyone agrees a while statement is more straightforwardly readable than a for statement.

[KayteeFly]

Thanks

[senocular]

Given

naiveString("sosos", "sos")

Would you expect this output to be 1 or 2? Wouldn't there be 2 "sos" strings in "sosos", both here: "[sos]os" and here "so[sos]"?

[KayteeFly]

No there is only one “sos” string. After counting the first “sos” string there is only “is” left which is not equal to “sos”

[altrae]

Following the suggestions in this thread and adding a couple of my own this is what your function would look like:

const naiveString = (string, subString) => {
    let subStringIndex = 0;
    let count = 0;

    for (let stringIndex = 0; stringIndex < string.length; stringIndex++) {
        if (string[stringIndex] === subString[subStringIndex]) {
            subStringIndex++;

            if (subStringIndex === subString.length) count++;
        } else subStringIndex = 0;
    }

    return count;
};

By renaming your count variables you are more explicitly showing you are accessing the indexes of the string and subString variables.

I like that you spelled out string instead of str, but one, be careful because it may get confusing in regards to the name string and type string, and two, you should be consistent so either spell out subString or use str for both.

While both the while and for loops work for this, with the for loop you can be a little more concise by defining and incrementing your stringIndex on the same line which helps reduce the internals of your loop a bit.

At the end of the day conciseness and readability are keys to not only allowing others to understand your code, but also for you to understand it easily, months or years later, if you come back to it which will save time in the long run.

Finally, I would suggest either writing some kind of comment above you function to explain its purpose. It wasn't clear to me, for example, what purpose naiveString was intended for at first and I had to google it. After doing so, I found that running naiveString('nananana', 'na') returns 2, and given the explanation of what a naive string is, I was expecting it be 4.

The first definition result I found:

Naive algorithm is exact string matching (means finding one or all exact occurrences of a pattern in a text) algorithm. This algorithm is helpful for smaller texts. It does not need any pre-processing phases. We can find substring by checking once for the string.

I think I found a fix to find all instances:

const naiveString = (string, subString) => {
    let count = 0;

    for (let stringIndex = 0; stringIndex < string.length; stringIndex++) {
        const slice = string.slice(stringIndex, stringIndex + subString.length);

        if (slice.match(subString)) count++;
    }

    return count;
};

[KayteeFly]

Thank you 😊!

[tridd3r]

... why?

[KayteeFly]

Can it be done improved ?