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 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]