The Aho–Corasick algorithm (1975) builds a single automaton from a whole dictionary of patterns so that a text can be scanned once, left to right, to find every occurrence of every pattern simultaneously — in linear time. It starts by building a trie (a tree of shared prefixes) of all patterns, radiating outward from the root here in 3D. It then adds failure links (orange arcs) that let the automaton "fall back" to the longest proper suffix of what it has matched so far that is still a prefix of some pattern, instead of restarting from the root on every mismatch.
Aho–Corasick is the classic engine behind multi-pattern text search: early
versions of the Unix fgrep command used it, and it still
underlies many antivirus signature scanners and network intrusion
detection systems that must check a stream against thousands of patterns
at once.
A 3D trie automaton radiates outward from a root node, its teal "goto" edges spelling out a dictionary of patterns and orange failure-link arcs showing how the algorithm falls back without ever rescanning the input.
All patterns share one trie built from their common prefixes. Failure links, computed once by breadth-first search, redirect a mismatch to the longest suffix of the current match that is still a valid prefix — so the whole dictionary is matched in a single linear pass over the text.
Edit the pattern dictionary and input text, then build the automaton. Press Play or Step to watch the glowing cursor walk goto edges (green) and failure links (orange) character by character, lighting up gold-ringed states whenever a pattern is matched.
Aho–Corasick runs in time proportional to the input length plus the number of matches — completely independent of how many patterns are in the dictionary — which is why it still powers many antivirus and intrusion-detection signature scanners today.