Suffix Trees
A suffix tree indexes all suffixes of a string in a compressed trie, answering many substring queries in time independent of the text length.
Every suffix in one tree
A suffix tree is a compressed trie containing every suffix of a string. Each suffix corresponds to a unique root-to-leaf path, and edges are labelled with substrings rather than single characters, so chains of single-child nodes are collapsed. Once built, the tree turns questions about the text into simple tree walks.
What it answers fast
Because every substring of the text is a prefix of some suffix, checking whether a pattern of length m occurs is just a walk of length m from the root, taking O(m) regardless of how long the text is. Counting occurrences is counting leaves in a subtree. The longest repeated substring is the deepest internal node, and the longest common substring of two strings is found by building a tree over both.
- Substring search: O(m) for a pattern of length m
- Count occurrences: leaves below the match node
- Longest repeated substring: deepest internal node
- Construction: O(n) with Ukkonen's algorithm
Linear-time construction
Naively inserting all n suffixes would take quadratic time, but Ukkonen's algorithm builds the suffix tree in O(n) by adding characters one at a time and reusing suffix links that jump between related nodes. The construction is intricate, which is one reason many practitioners prefer the simpler suffix array.
The suffix array alternative
A suffix array is the sorted list of all suffix starting positions. It uses far less memory than a suffix tree and, paired with a longest-common-prefix array, answers many of the same queries with binary search. Suffix arrays have largely displaced suffix trees in practice for their smaller footprint, though the suffix tree remains the clearer mental model for what is being indexed.