= Aho-Corasick automaton
{c}
An <Aho-Corasick automaton> augments a <trie> with a <failure link> from each nonroot state to its longest proper <suffix> that is also a <trie> <prefix>. Terminal states identify completed pattern <strings>; an <output link> points to the next terminal state along the <failure link> chain. The root represents the empty <string>. These structures support the <Aho-Corasick algorithm>.<Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick>[abstract, finite-state pattern-matching machine]{ref}
For pattern <strings> `ab`, `bab`, `bc`, the state `bab` has <failure link> to terminal `ab`, so both occurrences are reported after reading `bab`. If the next character is `c`, no <edge> leaves `bab` on `c`; following <failure links> reaches `b`, whose <edge> leads to `bc`. Reporting only the deepest terminal state would miss the simultaneous `ab` match.
A completed transition table stores the final destination for every state and <alphabet> character, giving one table lookup per input character. A sparse representation stores only <trie> <edges> and follows <failure links> on demand. They implement the same state invariant; the relevant space and lookup costs depend on the <alphabet> representation.
Back to article page
