4 Rabin–Karp Algorithm
This chapter covers
- Explaining a string matching algorithm to search a pattern within a given text
- Constructing robust hash functions to prevent collisions
- Applying rolling hashes to bypass the O(nxm) brute-force computational bottleneck.
- Analyzing algorithmic complexity, worst-case degradation, and performance.
In the previous chapters, we implemented and examined the Gale-Shapley Algorithm. The Gale-Shapley algorithm performed matching between two equal sets of participants. The matching should be stable based on the preferences provided. We covered the real-world applications of the Gale-Shapley algorithm along with its efficiency, tradeoffs, and key insight. This chapter focuses on one of the most widely used and discussed string-matching algorithms, called the Rabin-Karp algorithm.
The Rabin–Karp algorithm, created by Richard M. Karp and Michael O. Rabin in 1987, is a string-matching algorithm that matches a pattern inside a large string in a fast and efficient way. Instead of comparing every character of the pattern with every character of the text, the algorithm uses a hash function to convert the pattern into a numerical value. It then computes the hash values of different windows in the large input string and simply compares numbers instead of doing character-by-character matching. This is what makes the algorithm efficient, numeric comparison is much faster than comparing multiple characters.