The Karp-Rabin algorithm works by calculating a hash of the pattern and
comparing that hash with the hash of a slice of the target string with
the same length as the pattern. If the hashes are equal, the slice of the
target is compared to the pattern character by character (since the hash
function generally isn't injective).
For a single pattern, this tends to be more efficient than the naïve
algorithm, but it cannot compete with algorithms like
Knuth-Morris-Pratt or Boyer-Moore.
However, the algorithm can be generalised to search for multiple patterns
simultaneously. If the shortest pattern has length k, hash the prefix of
length k of all patterns and compare the hash of the target's slices of
length k to them. If there's a match, check whether the slice is part
of an occurrence of the corresponding pattern.
With a hash-function that
allows to compute the hash of one slice in constant time from the hash
of the previous slice, the new and the dropped character, and
produces few spurious matches,
searching for occurrences of any of n patterns has a best-case complexity
of O(targetLength * lookup n). The worst-case complexity is
O(targetLength * lookup n * sum patternLengths), the average is
not much worse than the best case.
The functions in this module store the hashes of the patterns in an
IntMap, so the lookup is O(log n). Re-hashing is done in constant
time and spurious matches of the hashes should be sufficiently rare.
The maximal length of the prefixes to be hashed is 32.