Suffix Trees
A Suffix Tree is a compressed trie containing all suffixes of a given text, offering O(M) pattern matching at the cost of high memory usage.
The Ultimate String Index
If you take all the suffixes of a string and insert them into a Trie, you get a Suffix Trie. While extremely powerful, it wastes massive amounts of memory on long paths with no branching. A Suffix Tree solves this by compressing non-branching paths into single edges.
O(M) Pattern Matching
Once a Suffix Tree is built for a massive text of length N, searching for a pattern of length M takes exactly O(M) time. The search time depends only on the length of the pattern being searched for, completely independent of the size of the underlying text.
Terms, operations, and practical uses
Structure
- Suffix TrieA standard Trie containing all suffixes of a text. Has O(N²) nodes, making it unusable for large documents.
- Path CompressionMerging all nodes that have only one child into a single edge that represents a substring instead of a character.
- Implicit NodesA location along a compressed edge. Search algorithms can stop 'inside' an edge without a physical node existing there.
Capabilities
- O(M) SearchSearching for a pattern of length M takes exactly O(M) time, completely independent of the massive text size N.
- Suffix LinksPointers from an internal node representing string
awto the internal node representingw. Crucial for linear construction. - Generalized TreeA single Suffix Tree can index multiple documents by appending unique terminal characters (like
$and#) to each text.
Ukkonen's Algorithm
- Online ConstructionBuilds the tree character by character from left to right, allowing processing of streaming text.
- Active PointA triplet
(active_node, active_edge, active_length)that tracks exactly where the next character insertion should occur. - Linear TimeDespite complex internal rules (extension rules, active point updates), amortized analysis proves it builds the tree in O(N) time.
Compress suffix-trie paths
# Conceptual Node for Suffix Tree
class SuffixTreeNode:
def __init__(self):
self.children = {}
# Edges store start/end index instead of characters
self.start = -1
self.end = -1
root = SuffixTreeNode()
root.start, root.end = 0, 5
print('Tree Compressed')struct SuffixTreeNode {
map<char, SuffixTreeNode*> children;
int start, end;
// In Ukkonen's, we use indices [start, end]
};class SuffixTreeNode {
Map<Character, SuffixTreeNode> children = new HashMap<>();
int start, end;
// Edges represent compressed string indices
}suffixes of the displayed textTree CompressedRun the example step by step
Ukkonen's Algorithm
The theoretical power of Suffix Trees was historically held back by their O(N²) construction time. Ukkonen's Algorithm revolutionized string processing by building the compressed tree in strictly O(N) time online, adding characters one by one.
Trees vs Arrays
While Suffix Trees are theoretically faster for certain traversal operations, Suffix Arrays (paired with LCP arrays) have largely replaced them in modern competitive programming and genomics. Arrays achieve the same theoretical bounds but use significantly less memory and have far smaller constant factors.