String Searching Algorithms
Learn about two powerful string searching methodologies: the Rabin-Karp algorithm and the Knuth-Morris-Pratt algorithm!
Start
Implementing the Rabin-Karp Algorithm in Python
Lesson 1 of 2
- 2To 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 …
- 3Great 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…
- 4It 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…
- 5In 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 …
- 6We 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…
- 7You 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…
- 8We 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…
What you'll create
Portfolio projects that showcase your new skills
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory