Rabin-Karp Substring Search

The Rabin-Karp substring search algorithm is doubly clever, for it relies not on one, but two clever tricks to perform substring search in O(N) time.

The first trick is that it performs a hash function to convert the needle and haystack window into integer hash codes. That is, the entire needle becomes a single integer, and so does the haystack window. If these two integers are the same, it means that the needle and haystack window are the same.

The reason this is a big deal is that, as I noted earlier, it takes multiple steps to compare our needle to a section of the haystack. That is, comparing "aaab" to "aaaa" or "ddde” to "dddd" requires us to perform up to four comparisons. But when it comes to comparing two integers, well, a computer can do that in a single step, assuming that the integers aren’t terribly long. Even if the integers have multiple digits, computers compare integers in constant time, something they cannot do with strings.

For example, say we use a hash function to first convert "ddde" into the integer 3334 and "dddd" into the integer 3333. At this point, the computer only has to perform a single-step comparison of integers 3334 with 3333 to know that there’s no match.

Now, the potential flaw with this first trick is that although comparing integers takes constant time, it takes multiple steps to hash all the characters of a string into an integer. This is because a hash function needs to perform a computation with each and every character of the string to produce a hash code.

For example, let’s say our hash function works like this: We convert each character with a number according to the scheme that "a" = 0, "b" = 1, "c" = 2, "d" = 3, and so on. So, "cab" would become 201, and "bad" would become 103. However, this still requires the hash function to process each letter to convert it into its corresponding numerical digit. If a string has 100 characters, this would take 100 steps. So, while the first trick is nice in theory, it would seem that it doesn’t save us any time.

But this is where the second trick comes in. The second trick is that we use—you guessed it—the sliding window technique so that we never have to hash the same character more than once.

Now that you’ve seen the two “tricks” we’ll be using, let’s get into the fine details.

Rabin-Karp in Action

First, we’ll look at a simplistic version of the Rabin-Karp algorithm, and from there, we’ll move on to a more sophisticated approach. In this simplistic model, we’re going to work with text that only contains the letters a through j. That is, we’re going to deal with an alphabet that contains only 10 letters. We’ll use the same scheme we did earlier, where a is 0, b is 1, all the way up to j, which is 9. (Later, we’ll extend this to the full 26-character English alphabet.)

Now, say we want to find the needle "cafe" within the haystack "decafcafeahead". In the following diagrams, I put each letter’s corresponding number right above it for ease of reference.

We’re now ready to launch the Rabin-Karp substring search algorithm.

The first thing the algorithm does is perform our hash function on the needle "cafe", turning it into a hash code of 2054 as shown in the .

Now, it may seem straightforward to perform this conversion; after all, we’re simply mapping each letter to its corresponding number. However, there’s a tad more math going on here than first meets the eye. But we’re going to defer that discussion until the next section. Let’s get a simple overview of Rabin-Karp first.

At this point, all we’ve done so far is hash our needle. Going forward, Rabin-Karp performs the following steps:

Step 1: We establish a “window” at the beginning of the haystack. Throughout the algorithm, the haystack window will always be the same length as the needle. In our example, the window spans four letters. We next hash this haystack window, and compare its hash code to the needle’s hash code:

Because the haystack window hash code is 3420 and is most certainly not equal to the needle’s hash code of 2054, we know that our haystack window and needle do not match. The next step is where the sliding window technique kicks in. Going forward, I’m going to refer to the haystack window simply as the “window.”

Step 2: We slide the window one letter to the right, encompassing the letters "ecaf". Now, we could hash this new, second window of "ecaf" in the same way we did our first window of "deca", but this would take too much time. Instead, we perform our sliding window trick, relying on the fact that the windows "deca" and "ecaf" share the same letters "eca" (which hashes to 420). The only differences are that the first window had an extra "d" at the beginning and the second window has an extra "f" at the end. So, we do this:

That is, we drop the initial 3 and tack on a new 5 at the end. Brilliant, right? The 420 part doesn’t have to change at all since both windows have that in common. This saves us from hashing the 420 digits again; we’ve already done that when we processed the first window. (Again, I’m glossing over some of the math for the moment.)

At this point, our current window is "ecaf", and our sliding window hash function computed its hash code of 4205. Because our needle’s hash code is 2054, this means we have not found our match.

Step 3: The next step is to slide the window another notch to the right:

Applying the same sliding-window-hashing technique described earlier, we drop the old 4 from the beginning and tack on a 2 at the end, giving us a new hash code of 2052. While this isn’t far off from our needle’s hash code of 2054, it’s not on the nose, so we have yet to find a match.

To move things along, we’ll skip Steps 4 and 5 and get to the punchline.

Step 6: After sliding the window three more notches, we get this:

Here, the current window computes a hash code of 2054, which is an exact match of our needle’s hash code. This means we found a match! Indeed, both the window and our needle are the same characters, "cafe".

The Rabin-Karp Hash Function

The hash function described in the previous section seems pretty simple. We take a string, such as "bcd", and convert it into an integer based on the number that each character corresponds to. Because b is 1, c is 2, and d is 3, we convert "bcd" into 123.

This hash function would be as simple as I described it if we were converting the string "bcd" into a string that was "123". But we’re not. We’re converting the string "bcd" into the integer 123. As noted earlier, the reason why we make the hash code an integer is that it’s faster to compare two integer hash codes than it is to compare two string hash codes. The thing is, though, that it takes a little math to convert a string into an integer.

To understand why this is so, you need to close your eyes and take a trip down memory lane. Picture yourself as a student in the third-grade classroom. At the front of the classroom, Mrs. Wilson was up at the chalkboard (remember those?) and teaching math. She was pontificating about the true meaning behind multidigit numbers, that is, numbers that contain more than one digit. On the chalkboard, she demonstrated that the meaning behind the number 2,054 is actually:

That is, the 2 in 2054 represents the thousands place, the 0 the hundreds place, the 5 the tens place, and the 4 the ones place.

Okay, you can open your eyes now.

Based on what Mrs. Wilson taught us, if we want to convert "cafe" to 2054, our hash function cannot simply convert the c from "cafe" into a 2. It needs to convert the c into a 2000.

So, to convert the entire string "cafe", we need our hash function to do the following:

This isn’t terribly complicated, and we’ll look at the code for this in a little bit. In any case, this is the hash function we’ll use to hash our needle and the first window from our haystack. Now, let’s move on to how our hash function should work as we slide our window through the haystack.

Let’s back up to the beginning of our example. We started off by hashing the first window of "deca" into 3420:

So far, so good. We just saw how this hash function works.

In the next step, though, we did this:

Now, what the hash function does here is not identical to hashing the first window. Because we’re using the sliding window technique, we don’t bother to hash "ecaf" from scratch. Instead, we eliminate the starting 3 from the previous hash code, and the only new item we need to hash is the final "f". This becomes a 5, which we tack on at the end of 420, turning 420 into 4205. So how does this hash function work, exactly?

The thing here is to remember Mrs. Wilson. We’re dealing with multidigit numbers, so we need to reckon with our thousands place, hundreds place, and so on.

The sliding window hash function goes like this. (I’ll show you a visual depiction of the computation first, and then explain it.) Here’s how we convert 3420 into 4205:

Let’s break this calculation down. Again, our goal is to do two things to the 3420 in order to convert it into 4205: we need to drop the initial 3, and we need to tack on a 5 at the end.

First, we drop the starting 3. Because that 3 represents 3000, we need to subtract 3000 from 3420 to eliminate that 3. This leaves us with a remainder of 420.

Now, you and I know by looking at the 3420 that its 3 represents 3000. But a computer didn’t take Mrs. Wilson’s class, so somehow, we need to tell the computer how to convert that 3 into 3000. In other words, how do we get the computer to understand that the 3 represents the thousands place?

The key is understanding that what the first digit represents is tied directly to the haystack window size. When the window size is 4, the first digit will represent the thousands place. But if our window size was 3, then the first digit is the hundreds place, and if the window size was 5, then the first digit would represent the ten-thousands place.

So, to figure out what number to multiply the first digit by, we take 10 and raise it to the power of the window size minus 1. In our example, the window size, 4, minus 1 is 3. When we raise 10 to the power of 3, we get 1,000. We can then multiply this number by our first digit to see what the first digit represents. In our case, where the first digit is 3, this gives us 3000.

If our window size were 5, then we’d raise 10 to the power of 4 and get 10,000. If our first digit is 3, we’d know that the 3 represents 30000.

In any case, in our example, we’ve computed that the first digit represents 3000. And so, when we subtract that from 3420, we end up with 420, which means that we successfully dropped the initial 3. Our next step is to convert the 420 into 4205.

Thankfully, this part is a little more straightforward. We convert the 420 into 4200 by multiplying it by 10. In effect, this moves each digit one notch to the left to make room for our new digit. Once we have this result of 4200 in hand, we simply add the new, final digit of our current window to it. Since in our example the final digit is 5, this gives us 4205.

By the way, a hash function that employs the sliding window technique is known as a rolling hash function.

Note that our hash function for hashing the first window (as well as the needle) is a plain old regular hash function. I’ll refer to this as the “initial hash function.” But the hash function we use for hashing the second and subsequent windows is the “rolling hash function” I just described.

Whew! Now that we’ve seen how our hash function works, let’s write up some code.

Code Implementation Rabin-Karp for Base 10

Our current illustration of the Rabin-Karp algorithm is still a simplistic variant, but we’re not far off from the full algorithm. However, let’s spin up some code for what we’ve covered so far:

Here, our primary method is find_needle, which accepts both the haystack and needle arguments. If the needle is found, the method will return the index of where the needle’s first character is found within the haystack. If the needle is nowhere to be found, we return None.

The find_needle method relies on the two hash functions I described earlier, namely, our initial hash function and our rolling hash function. I placed the code for these hash functions in their own distinct methods: initial_hash and rolling_hash, respectively.

First, the find_needle method performs the initial_hash function on the needle and the first window of the haystack. This provides us with the hash codes of both the needle and the first haystack window. At this point, we check whether the hash codes are the same, which would indicate that the needle and haystack window are both the same. If they are, we return 0 to indicate that the needle can be found at index 0 within the haystack.

If we don’t have a match, we then begin a loop that iterates over almost every index of the haystack. We begin at index 1, and end at whichever index will be the first character of the final window. Within this loop, we identify the drop_character, which is the first character of the old window. Likewise, we locate the new_character that is being introduced as the final character of the new window.

We compute the new window’s hash code by performing the rolling_hash function, and then check to see if the new window’s hash code matches the needle’s hash code. If we find a match at any point, we return the current index, which is where our current haystack window begins. If we get through the entire haystack without finding the needle, we simply return None.

The initial_hash and rolling_hash functions track with the math I described earlier. Note that they both rely on yet another function, character_hash_code, which returns the hash code for a single character. I’ve set it up so that "a" will return 0, "b" will return 1, and so on. To do this, I subtract 97 from whatever Python’s built-in ord function returns since ord("a") is 97, and ord("b") is 98, and so on, corresponding to the characters’ ASCII codes.

Collision Ahead

Although we’ve seen the gist of the Rabin-Karp algorithm, we need to iron out a few more details. The first item is that, until now, we’ve dealt with examples where our strings only contain letters a through j. Ultimately, though, we want our algorithm to work with the full 26-letter English alphabet. In fact, we want it to work for even larger character sets that include lowercase and uppercase letters, numbers, punctuation marks, and more. Indeed, the full ASCII character set contains 256 possible characters. But for now, let’s deal with the set of 26 lowercase alphabet letters.

Here’s why we care about the size of the character set.

Let’s extend our letter-to-number scheme to the rest of the alphabet, even beyond the letter j. So h corresponds to 10, i corresponds to 11, and so on, until z, which corresponds to 25. (The letter a corresponded to 0, so our final letter, the z, ends at 25.)

Here’s what happens if we try to hash the word "hazy":

While this computation seemed to work out, there’s a subtle flaw here.

Let’s zero in on the "z" and the "y". In fact, let’s pretend that the entire string was just "zy". If we hash "zy" according to this method, we get 274.

The problem is that "zy" isn’t the only string that has a hash code of 274. After all, "che" also hashes to 274.

This was not a problem when we only dealt with letters a through j, though. Because there are only 10 possible characters, we are guaranteed that each character’s corresponding digit (0 through 9) will only take up one “place” in the larger number. That is, if the final character of our string is "e", its corresponding number of 4 will be entirely contained within the ones place. Even the highest available character—"j"—corresponds to 9, which is a single digit.

But if our final letter is "k", which corresponds to 10, that’s a double-digit number, so the hash code “bleeds” from the ones place into the tens place. This, in turn, introduces the problem we saw earlier. That is, the hash code 10 could represent "k", but it could also represent "ba" since "b" is 1 and "a" is 0. There’s no longer a way to know for certain what string a given hash code is supposed to represent.

In fact, you can even have two different strings of the same length that convert to the same hash code. For example, both "lk" and "ma" have the hash code 120. This is because "m" is equivalent to 12, and "a" is 0. Because the a converts to a single digit, it doesn’t bleed at all into the tens place. This gives us a hash code of 120 since we have 12 tens and 0 ones.

But the string "lk" is an entirely different story. The character "l" converts to 11, and "k" converts to 10, which is also two digits. This 10 bleeds from the ones place into the tens place, and also causes "lk" to have a hash code of 120. That is, we have 11 tens, and 10 ones. This is 110 + 10 = 120.

Our algorithm might mistakenly think it found a match if our needle is "lk" and the haystack window is "ma"! Because of this, our hash function needs to make sure that when we convert a string into a numerical hash code, each character of that string converts into a number that can be contained within a single digit place.

So, how do we apply Rabin-Karp to a character set that contains more than ten letters?