Even though the Boyer-Moore string search algorithm is the standard benchmark for practical string search literature, there are other string matching algorithms that are also suitable for different purposes. In this small section, we present the following three, which are the most famous ones:
- Rabin-Karp
- Knuth-Morris-Pratt
- Aho-Corasick
However, only give out the implementation of Rabin-Karp.
In 1987, Richard M. Karp and Michael O. Rabin proposed a string matching algorithm that performs well in practice and generalizes string matching against a set of patterns. The Rabin-Karp algorithm takes O(m) time in its preprocessing stage and its worst-case running time is O((n - m + 1)m), similar to Boyer-Moore's.
To better introduce the Rabin-Karp algorithm, let's assume that our alphabet ∑ is composed only of decimal digits (∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}), so that we can view a string of k characters as a decimal number with length k. Therefore...