the Aho-Corasick algorithm
/ AH-ho kor-AH-sick /
Suppose you must scan a stream of text for any of thousands of forbidden words — a spam filter, a virus scanner matching many signatures, or a search that flags any keyword from a list. Running a single-pattern matcher once per word would cost time proportional to the text length times the number of words. Aho-Corasick finds all occurrences of all the words in essentially one pass over the text, no matter how many words are in your dictionary.
It works by first building a trie of all the patterns: a tree where shared prefixes share a path (so "he", "her", "his" overlap near the root). Then it adds failure links, the multi-pattern generalization of KMP's failure function: from each trie node, a failure link points to the node representing the longest proper suffix of the current matched string that is also a prefix of some pattern. Now scan the text one character at a time, walking down the trie when the next character matches an edge, and following failure links when it does not — exactly like KMP, but across all patterns simultaneously. Whenever you pass through (or a failure link reaches) a node marking the end of a pattern, you report that occurrence. Building the automaton is O(total length of all patterns), and scanning is O(n + number of matches reported). That last term matters: if many patterns overlap at one spot, reporting them is unavoidable work.
Aho-Corasick, from 1975, is the standard tool for dictionary matching and powers classic tools like fgrep and many intrusion-detection and bioinformatics systems. Its great virtue is that the cost barely depends on the number of patterns — adding more words to the dictionary makes the automaton bigger but does not slow the per-character scan. The mental model worth keeping: it is KMP with a tree instead of a line, where the failure links let a single text scan track partial matches of every pattern at once.
Dictionary {"he", "she", "his", "hers"}, text "ushers". Scanning, at "...she" we are at the node for "she"; its failure link points to the node for "he", so we also report "he". Continuing through "hers" reports "hers" too. One left-to-right pass found "she", "he", and "hers" — overlapping matches included — without restarting per word.
A trie of all patterns plus KMP-style failure links matches every dictionary word in one text pass.
The output-sensitive term O(matches) is unavoidable: if a position ends many dictionary words at once, you must report them all. A subtle point is that you also need 'dictionary suffix links' so that ending one pattern also surfaces every shorter pattern that ends there.