In this lesson, we will implement the Rabin-Karp algorithm discussed in the previous article using Python. We assume that you are familiar with most of the common data structures and algorithms by now, so this lesson will be a step towards delving into somewhat advanced algorithmic territory!
We can use the Rabin-Karp algorithm to find all occurrences of a pattern in a given text. We can implement this in several ways but the core idea of the algorithm remains the same — instead of matching the pattern against a substring in the text character-by-character, we will use string hashing to compare them almost instantly. To bring the algorithm to life, here is what we will do in the exercises that follow:
- Quickly recap naive pattern-matching by implementing a brute-force algorithm to locate a pattern in a given string.
- Refresh our understanding of hashing by performing some hashing operations on strings.
- Explore different hash functions to increase efficiency in pattern-matching.
- Optimize the Rabin-Karp algorithm for peak performance.
Let’s get started with tackling each of these steps.
To the right is a comparison of a brute-force pattern search vs. Rabin-Karp. Recalling what you reviewed in the article, why is the Rabin-Karp search so much faster?