Share pattern prefixes in a trie
Aho–Corasick preprocesses a dictionary of patterns into one automaton and scans the text sequentially. The initial trie shares common pattern prefixes. A state describes a dictionary prefix matching a suffix of text read so far. A plain trie alone lacks enough information to resume after a mismatch without restarting searches. A failure link identifies the longest proper suffix of the current state’s string that is also represented as a trie state. This relationship generalizes the reuse of matched structure in a single-pattern search to a whole dictionary.
Report suffix matches as well
Use patterns he, she, his and hers with text ushers. On completing she, the automaton must report both she and its suffix he. Later r and s complete hers. Their zero-based starting positions are one for she and two for both he and hers. Reporting only the terminal pattern attached directly to the current state would miss he. Output information associated through failure relationships is therefore essential. Multiple patterns can end at one text position, and occurrences can overlap; these are valid results rather than duplicates to discard automatically.
Count failure and output work
Failure links are commonly built in breadth-first order so that shorter states are available before deeper ones. During searching, a missing direct transition follows failure links until a suitable transition or the root is reached. With an appropriate fixed-alphabet or constant-time transition representation, searching is O(n+z), where n is text length and z is the number of reported occurrences. Output cannot be ignored in the bound. Copying every inherited output list into every state can inflate preprocessing and space; output links or another explicit representation should be described when claiming a compact construction.
Define representation and updates
A dense transition table uses space proportional to the number of states times alphabet size. Sparse child dictionaries have different lookup and construction costs, which must be counted rather than assumed away. Adding a new pattern may change failure and output relationships, so updating an established automaton is not always just adding a trie branch. Empty patterns require a convention about matching every boundary, and duplicate strings registered under separate identifiers need a defined reporting policy. Finally, substring detection does not itself impose word boundaries or language-aware tokenization. Those application requirements must be added explicitly to the matching interface.