Aho-Corasick
A trie of all patterns plus failure links; matches many patterns in one pass over the text.
Node "he": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a e child there.
What you will see
The text walks the trie; failure links jump on mismatch; output links report matches.
Cost
| Best | O(n + total pattern length) |
|---|---|
| Average | O(n + z) |
| Worst | O(n + z) |
| Space | O(total pattern length * alphabet) |
z is the number of matches.
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Text and pattern cells announce index and character; each step announces the aligned positions, the comparison result and the shift.
Reduced motion: The pattern row snaps to its new alignment with a crossfade instead of sliding.
Before this
Taught by the same lesson
Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.