Aho-Corasick automaton

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.^[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.

An output link in an Aho-Corasick automaton points to the nearest terminal state encountered strictly after the current state on its failure link chain. It skips states that do not end a pattern string. After reading a text character, report a pattern at the current state if terminal, then follow output links to report its terminal suffixes.

For dictionary strings a, ba, aba, reaching state aba reports all three patterns ending at that position. Its output link reaches ba, and the next reaches a. Reporting only aba would miss two valid occurrences. The current state's own match is handled separately because an output link points to a proper suffix, not to itself.

If $f(q)$ is the failure link destination, the output link is $f(q)$ when that state is terminal, and otherwise the output link of $f(q)$. Build this information in increasing trie depth, so the shorter failure states are already available. Traversing only terminal links makes reporting cost proportional to the number of emitted matches, rather than the length of every nonterminal failure chain.^[ref]