Brute-Force Substring Search

The idea behind brute-force substring search is to use two loops to search the haystack. The outer loop combs through each character of the haystack one at a time, and when it finds a character that matches the first character of the needle, an inner loop begins. Before we get to the inner loop, though, let me show you what I’m talking about.

Say that our needle is the string "bet" and the haystack is the string "flibbertigibbet". (Of course that’s a real word. A flibbertigibbet is an excessively talkative person.) We begin with two pointers, one that points to the needle’s first character, and the other that points to the haystack’s first character:

We check if the two characters match. Currently, they don’t, so we move the haystack’s pointer onward:

Again, the haystack’s letter "l" does not match the needle’s letter "b", so the haystack pointer needs to move on. Let’s skip to the exciting part, where the haystack and needle pointers do match:

Oh, a match! Both pointers point to "b"s. Now, this is when we begin the inner loop I mentioned earlier. That is, we keep the haystack pointer in place, but set a new, second haystack pointer—represented by an emoji in the diagram —to scan the rest of the needle. I’ll call this second pointer the “emoji pointer.” (I want to give this pointer a unique name, so there it is.)

After initializing the emoji pointer, we move the needle pointer along to the next character. We then check whether the needle pointer and the emoji pointer point to matching letters.

The emoji pointer is sad because the "b" that it points to does not match the "e" of the needle pointer. This means that we have not found our matching substring—yet.

To continue our search, we terminate our inner loop and get rid of the emoji pointer for the time being. We reset the needle pointer to point back to the needle’s first character and begin the next round of the outer loop. As we’ve done with the previous rounds of the outer loop, we next compare the haystack and needle pointers to see if we have a match:

And sure enough, we do! This means we begin an inner loop once again, which also means we get to bring our emoji pointer back, and also increment our needle pointer. We then check to see whether the emoji pointer and needle pointer yield a match:

This is terribly exciting because the emoji pointer and needle pointer both point to an "e"! We now have matching substrings of "be". Are we about to find our needle of "bet"? Well, let’s move the emoji and needle pointers along and see:

Bummer, it’s not a match. Our inner loop terminates, and we’ve got to reset our needle pointer back to the beginning, dispense with the emoji pointer, and move on. We’ll skip a few steps once again and reach the climax of our search:

The "b"s match, so we fire up an inner loop. We activate our emoji pointer and move the needle pointer along:

Again, a match! Will we, once and for all, find our complete needle?

You bet! At this point, our algorithm will return the haystack index where the beginning of the needle can be found.

And that wraps up our brute-force substring search walkthrough.

Code Implementation: Brute-Force Substring Search

Here’s one way to implement brute-force substring search:

Here, the haystack_index serves as the haystack pointer and needle_index as the needle pointer. We get our “emoji pointer” by adding the haystack_index and needle_index together, rather than declaring an explicit “emoji pointer” variable (which would be weird).

Once the needle_index reaches the end of the needle, it means we found the needle in the haystack. Accordingly, we return the haystack_index, which is the location of the needle’s first character within the haystack.

The Efficiency of Brute-Force Substring Search

In many practical cases, brute-force substring search isn’t half bad in terms of speed. In looking at the previous example, our haystack pointer touched each haystack character once, which is O(N) if N represents the number of characters in the haystack.

For clarity’s sake, I’m going to use the variable H, instead of N, to refer to the number of haystack characters, with H standing for “haystack.” I will instead use N to refer to the number of characters in the “needle,” since “needle” starts with the letter N. In short, H is the number of haystack characters, and N is the number of needle characters. Got it?

So far, then, we can say that our haystack pointer will point to all H characters of the haystack.

The additional steps of the algorithm consist of moving the needle and emoji pointers, which we do in tandem within an inner loop. In the earlier example, we only launched this inner loop a handful of times. We also saw how the inner loop terminated after a couple of iterations before hitting a mismatch between the needle and emoji pointers. In fact, the inner loop will never run more times than the number of N needle characters. That is, if the loop does manage to run N times, that means we’ll have scanned the entire needle, and there’s nothing left for the loop to do. By that point, we’ll know whether the needle was found at that point in the haystack or not.

In the earlier walkthrough, only a handful of inner loop steps were executed. We might be tempted to simply discount those steps entirely and say that our algorithm ran in approximately O(H) time. Indeed, brute-force substring search does take O(H) time for average-case scenarios. However, as you know, when evaluating an algorithm’s efficiency, we also need to take into account the worst-case scenario.

Here’s an example of a kind of worst-case scenario for substring search. Say that the needle is "aaaab" and the haystack is "aaaaaaaaaaaaaaaaaaab". In this case, for every haystack character (save for the last few), we have to activate our inner loop. And the inner loop itself will scan the full length of the needle. Therefore, we’d say that brute-force substring search can take up to O(HN) in the worst case. This can be slow if we’re dealing with a lot of text.

Luckily, there are a number of algorithms out there that improve the performance of substring search. These are perhaps the three most famous:

• Knuth-Morris-Pratt (otherwise known as KMP)
• Boyer-Moore
• Rabin-Karp

All three of these algorithms run in O(H+N) time even for the worst-case scenario. Note that O(H+N) is much faster than O(HN).

Of these three algorithms, we’ll explore the Rabin-Karp algorithm. It ties in nicely with many of the concepts discussed earlier in this book, and it will also unlock a bunch of new and useful concepts. One of those new and useful concepts is a technique that many refer to as the “sliding window” technique. So, let’s kick things off with that.