AlgoScope

Suffix Tree

A compressed trie of all suffixes. Answers substring queries in O(m).

Data structures, data structure, expert
Fold the chain into the edge banan$.banan$•banan$anan$nan$$$$

Radix Tree, Suffix Tree, Aho-Corasick: Suffix tree of banan: every substring in one walk

Decision, step 8 of 12

From the root, the edge "b" leads into a chain of 5 nodes that each have one child and end no word. Nobody can branch off inside it, so the whole chain becomes a single edge labelled "banan$". 5 nodes gone.

How radix tree, suffix tree, aho-corasick works

Cost

Build
O(n)
Substring query
O(m)
Space
O(n)

Linear construction (Ukkonen) is out of scope for visualization in V1.

Taught by the same lesson

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