Wrapping Up

The Rabin-Karp algorithm uses a number of the techniques we’ve learned about in the past few chapters. From division hashing to Monte Carlo, we’ve pulled out all the stops. And the result is phenomenal: we’ve achieved linear-time substring search.

We also looked at the important concept of base number systems, which will also be crucial for the upcoming chapters. Finally, we’ve also seen how sometimes it’s possible to convert a Monte Carlo algorithm into a Las Vegas algorithm and eliminate the chance for any inaccuracies.

I recommend that you also check out other linear-time substring search algorithms such as KMP and Boyer-Moore, as they’re fascinating and use a completely different approach than Rabin-Karp. Indeed, each of the three algorithms has nuanced pros and cons. One of the pros of Rabin-Karp is that it doesn’t consume any extra space, while the other two algorithms do.

Over the past few chapters, you’ve learned how Monte Carlo algorithms can be used to speed up your code. I’ll have you know, though, that Monte Carlo algorithms can also be used to save space, as I’ll discuss in an upcoming chapter about Bloom filters. However, to understand Bloom filters, there’s a prerequisite concept I need to cover first—and that is the data structure called the bit vector.