AlgoScope

Aho-Corasick

A trie of all patterns plus failure links. Matches many patterns in one pass over the text.

String algorithms, algorithm, advanced
Failure link of he set.fff•hesheisrs
Failure link of he set.fff•hesheisrs

Radix Tree, Suffix Tree, Aho-Corasick: Aho-Corasick: he, she, his, hers in one pass

Decision, step 3 of 16

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.

How radix tree, suffix tree, aho-corasick works

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.

Taught by the same lesson

Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.