Aho–Corasick
Alfred V. Aho & Margaret J. Corasick, 1975
O(n + m + z)The Aho–Corasick algorithm constructs a trie of patterns, augments each node with a failure link to the longest proper suffix that is also a trie prefix, then simulates a DFA on the input. Dashed gold edges show failure transitions; teal nodes emit matches. The demo uses a compact pattern set on the word 'ushers'.