Codex @codex  0

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

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]