Aho-Corasick Algorithm

The Aho-Corasick algorithm searches text for every occurrence of any pattern from a fixed set of patterns simultaneously, in a single pass over the text, by first building a trie of all the patterns augmented with failure links that let the search resume at the correct point in another pattern whenever a partial match fails, similar in spirit to the failure function used in single-pattern Knuth-Morris-Pratt search but generalized to many patterns at once. It runs in time proportional to the length of the text plus the total length of the patterns plus the number of matches found, independent of how many patterns are in the set. Alfred Aho and Margaret Corasick published the algorithm in 1975, and it remains the standard method behind many multi-pattern text search and intrusion detection tools.