Naive String Search with and without Two Loops in Ruby and JavaScript

Since graduating from a software engineering coding bootcamp I have been spending most of my time getting a handle on the basics of computer science, specifically data structures and algorithms. Today I wanted to share the experience of the naïve string search since this has as its basic real-world implementation a crude text searching feature that one could use on their web site (with JavaScript on the frontend) or for searching through some long text storage in their database (with Ruby for the backend).

One thing I noticed about this string searching algorithm as the way it is often taught is that it requires two loops. I’ll show by example in Ruby how it functions using two loops. First, we need to define a method that takes in two arguments: The entire text to search through, and the fragment that one is searching for. We will being by setting up a loop to search through the longer text letter by letter. Then we will loop through the fragment to check if each letter of the fragment matches the text. For instance, if we were searching through the text “Mississippi” and wanted to count the amount of times “is” appeared in the word, whenever we matched “I” from the longer text, we’d then go onto check the next two letters of both strings to see if they also matched, until we’ve exhausted the length of the fragment. If we have a match, we’ll increase the counter by one. The code would look something like this:

def naiveStringSearch(string, frag)
  count = 0
  s = string.length - 1
  f = frag.length - 1
  for i in 0..s do
    for j in 0..f do
      if frag[j] != string[i+j]
        break
      elsif j==f
        count += 1
      end
     end
  end
  return count
end

Now, for the JavaScript example, I’d like to show how by using the slice() method we can not only eliminate the need for two loops, we can also reduce BIG O to less than “n” since we will end our loop through the longer text by the length of the fragment (though, I’m aware that this is not quite true since behind the scenes, .slice() is using a loop).

The way we are going to search here is to begin once again by setting up an iteration over the full text to be searched through. However, for each iteration, we are going to begin at the iteration point and take a look ahead the amount of characters that is equal to length of the fragment and then compare what we “sliced” out and determine if it is the same as the fragment. If so, increase the counter by one. The much shorter code looks like this:

function naiveStringSearchFaster(string, frag) {
     let count = 0
   for(let i=0; i < string.length - frag.length + 1; i++) {
       let check = string.slice(i, i + frag.length)
       if (check===frag) {
          count++
       }
    }
   return count
}

Two different ways to solve the same problem. Hopefully, someone will be able to comment on which one is actually faster in BIG O terms, or I will eventually solve that myself in a future post. Until then, be well!