Substring Search

When you’re working on your code in your text editor and you need to find the variable doris_the_cat somewhere within thousands of lines of code, it’s unlikely you’ll go scrolling down the code until the variable catches your eye. Instead, you’ll probably use your text editor’s “find” feature, in which you’ll enter doris_the_cat, or just doris, and your editor will immediately put the first instance of that variable in view. While most of us take this feature for granted, it’s not at all trivial to find the string doris_the_cat amid thousands of lines of code so quickly.

This problem is known as substring search. That is, we have some large body of text (such as a code file), and a smaller string (such as doris_the_cat), and we need to find the smaller string within the larger body of text. We can think of this as searching for a needle within a haystack. In computer science jargon, the needle is called the pattern, and the haystack is called the text. However, I’ll continue to use the terms “needle” and “haystack,” since the term “text” is vague and can make things confusing.

Numerous algorithms exist that solve substring search, and researchers are still on the lookout for even faster alternatives. We’ll look at a couple of them in this chapter, starting with brute force.