Implementing the Rabin-Karp Algorithm in Python
Lesson 1 of 2
  1. 1
    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 …
  2. 2
    To get a handle on a more advanced string-search algorithm like Rabin-Karp, it is a good idea to be comfortable with naive pattern-matching on a given string. In this exercise, we will refresh our …
  3. 3
    Great job so far! You are certainly an expert when it comes to searching for patterns using brute force. But judging from how long it took the last program to run, naive pattern-matching seems to b…
  4. 4
    It seemed like we were making decent progress, but our hash function collided to the same value! Indeed, there is only a limited set of values that we can generate using ASCII values. This is a pro…
  5. 5
    In trying to compute the hash values of all substrings, we can still bypass some of the calculations. That’s right! We don’t have to perform multiplication after multiplication to compute the hash …
  6. 6
    We saw a neat way to recover hashes using rolling hash, but unfortunately, we still ended up with a hashing collision in the case of palindromic strings. Simply multiplying primes will not make a g…
  7. 7
    You are probably wondering why we didn’t make use of any “rolling” property of the polynomial hash function and just calculated the hash values for all substrings by adding up the individual contri…
  8. 8
    We now have all the tools in place to complete the full implementation of the Rabin-Karp algorithm! All that is left is to compute the hash of the pattern and compare it with substrings of the same…
  9. 9
    Congratulations! You have reached a significant milestone in your programming career — implementing an advanced string-matching algorithm from scratch! Here is a quick recap of what we accomp…

What you'll create

Portfolio projects that showcase your new skills

Pro Logo

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo