Editing Rabin–Karp algorithm (section)

== Multiple pattern search ==
The Rabin–Karp algorithm is inferior for single pattern searching to [[Knuth–Morris–Pratt algorithm]], [[Boyer–Moore string-search algorithm]] and other faster single pattern [[string searching algorithm]]s because of its slow worst case behavior. However, it is a useful algorithm for [[String searching algorithm#Algorithms using a finite set of patterns|multiple pattern search]].

To find any of a large number, say ''k'', fixed length patterns in a text, a simple variant of the Rabin–Karp algorithm uses a [[Bloom filter]] or a [[set data structure]] to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for:

<syntaxhighlight lang="php" line>
function RabinKarpSet(string s[1..n], set of string subs, m):
    set hsubs := emptySet
    foreach sub in subs
        insert hash(sub[1..m]) into hsubs
    hs := hash(s[1..m])
    for i from 1 to n-m+1
        if hs ∈ hsubs and s[i..i+m-1] ∈ subs
            return i
        hs := hash(s[i+1..i+m])
    return not found
</syntaxhighlight>

We assume all the substrings have a fixed length ''m''.

A naïve way to search for ''k'' patterns is to repeat a single-pattern search taking O(''n''+''m'') time, totaling in O((''n''+''m'')''k'') time. In contrast, the above algorithm can find all ''k'' patterns in O(''n''+''km'') expected time, assuming that a hash table check works in O(1) expected time.