Aho-Corasick Multi-Pattern Matching
Build a dictionary automaton and replay one-pass text search with failure links, inherited suffix outputs and every overlapping match.
Free theory articleBuild a dictionary automaton and replay one-pass text search with failure links, inherited suffix outputs and every overlapping match.
Concept & interpretation
Aho-Corasick builds a finite automaton from a dictionary of patterns. It then reads a text from left to right and reports every dictionary word ending at each position, including overlaps and words that are suffixes of other words. A trie shares common prefixes; failure links preserve useful suffixes when the next trie edge is missing.