Aho-Corasick
A trie of all patterns plus failure links. Matches many patterns in one pass over the text.
Radix Tree, Suffix Tree, Aho-Corasick: Aho-Corasick: he, she, his, hers in one pass
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.
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.
Before this
Taught by the same lesson
Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.