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. a deterministic "o"("n"+"km") solution is the aho–corasick algorithm.