Aho-Corasick — One Trie, Failure Links, One Linear Scan

Build a trie of all patterns, compute failure links (the multi-pattern KMP prefix function) by BFS, then scan the text following goto/failure transitions and firing matches via output links.

step 0

Automaton (trie + failure links)

trie node pattern end current state failure link

Scan of the text

Current automaton state and the patterns ending here will show up as the scan advances.
Matches found (pattern @ end index):
none yet
Press Step to begin. We first build the trie and failure links, then scan the text one character at a time.
Self-contained visualization. Lowercase alphabet (a–z). Failure links (pink dashed) are the multi-pattern generalization of KMP's prefix function, built by BFS. A match at the current state fires via output links, so overlapping patterns (e.g. he inside she) are all reported. See junior.md and professional.md for the construction and the proof that the scan is O(n + z).