= Aho-Corasick algorithm
{c}
The <Aho-Corasick algorithm> reports occurrences of a finite collection of nonempty pattern <strings> in one <string>. It builds an <Aho-Corasick automaton> from their <trie>. Each scanned character extends the current state; when no <edge> matches, <failure links> find a shorter matching <suffix>. Report the current terminal pattern <string> and the terminal ancestors reached through <output links>.<Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick>[abstract, keyword-matching machine and single-pass search]{ref}
The state represents the longest <suffix> of the scanned text that is a <prefix> of some pattern <string>. This invariant explains correctness: a match ending now is exactly a terminal <suffix> represented by that state or a <failure link> ancestor. It also reports overlaps. With pattern <strings> `ab`, `bab`, `bc`, scanning `babc` reports `ab` and `bab` at position three, then `bc` at position four.
For a fixed-size <alphabet>, completed transitions and <output links> give $O(M+n+z)$ total time, where $M$ is total pattern <string> length, $n$ text length and $z$ the number of reported occurrences. The $z$ term is unavoidable when listing every match. Store terminal <output links> instead of copying every inherited match list: copied <suffix> lists can greatly enlarge preprocessing.
Back to article page
