= Output link
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 <string suffix>[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 <string suffix>[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.<Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick>[Keyword-matching machine; terminal suffix reporting, with the three-pattern example independently derived]{ref}
Back to article page
