Suffix Tree
A compressed trie of all suffixes. Answers substring queries in O(m).
Radix Tree, Suffix Tree, Aho-Corasick: Suffix tree of banan: every substring in one walk
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.
Cost
- Build
- O(n)
- Substring query
- O(m)
- Space
- O(n)
Linear construction (Ukkonen) is out of scope for visualization in V1.
Before this
Related
Taught by the same lesson
Radix Tree, Suffix Tree, Aho-Corasick covers these too, in the same run.