Naive String Searching Algorithm

(Javascript Implementation)

stringSearch implementation

Time complexity:

Worst Case: O(m*n)

How it works:

We’re going to create a function with a parameter for the givenString and a parameter for the pattern we’re looking for.

First let’s create a counter to count how many matches do we find.

Next, in order to compare the two strings, we need to create a loop to take care of all the indexes of the givenString and also an inner loop to compare the indexes.

While we are in the index 0 of the outer loop, the inner loop will check if the elements contained on the index 0 of the givenString and pattern are equal. If there is a match, the inner loop will move one index forward and will compare the pattern next element with the index +1 of the givenString.

It will do so until it founds a match on the pattern and then will add +1 to the counter.

Any time that the inner loop doesn’t find a match it will break, so the outer loop can move one index forward, allowing us to navigate through the whole givenString.

Take in consideration that this a brute-force approach with nested loops. It is very time consuming.

Let’s see some images to have a better understanding of what is happening.

This is the original string where we want to match the following pattern: “hello”.

The inner loop is going to run comparing the first element with the first index of the outer loop. It has found a match so it continues.

The first letter was a match but the following one is not, so the inner loops breaks.

The outer loop advances one index and we start to compare it with the inner loop. Because “i” is not wat we want to match the inner loop breaks again and the outer loop will move one index forward.

We repeat the operation, comparing the inner loop with the outer loop. Since we got a match, we compare the second index of the inner loop and the next index of the outer loop.

We continue the operation since “e” is a match.

We got another match.

Yeah, it seems like we are close to get the whole pattern!

Eureka! Found it! Now we add +1 to the counter since we’ve found 1 match.

We repeat the operation with all the indexes of the outer loop.

Not a match…

Still not a match …

Not a match neither …

Oh! Possible pattern match starts again!

Bad news… the next index is not a match….so we break again the inner loop and advance one index on the outer loop.

The last index is not a match. We finish this iteration since we run out of indexes to compare. We got one match in the whole string!

Pseudocode

// Define a function that takes 2 strings. The large one and the
   pattern we're looking for.
// Loop over the longer string.
// Loop over the shorter string.
// If the characters don't match, break out of the inner loop.
// If the characters do match, keep going.
// If you complete the inner loop and find a match,
   increment the count of matches.
// Return the count

Code