Suffix Tree
String indexing data structure
A suffix tree is a compressed trie data structure that represents all the suffixes of a given string, enabling extremely fast substring, pattern-matching, and string-analysis queries.
Definition
A suffix tree is a compressed trie data structure that represents all the suffixes of a given string, enabling extremely fast substring, pattern-matching, and string-analysis queries.
Overview
A suffix tree for a string S of length n is a tree in which every path from the root to a leaf spells out one of the suffixes of S (often with a unique terminating symbol appended to ensure no suffix is a prefix of another). Unlike a naive trie of all suffixes, which would require O(n^2) space, a suffix tree compresses chains of single-child nodes into single edges labeled with substrings, allowing the entire structure to be stored in O(n) space despite representing O(n^2) total suffix characters implicitly. Construction of a suffix tree can be done in O(n) time using Ukkonen's algorithm, a notable achievement given the structure's apparent complexity; earlier algorithms by Weiner and McCreight also achieve linear time but with different construction strategies. Once built, a suffix tree supports substring search in O(m) time (where m is the length of the query pattern), independent of the size of the original text — a dramatic improvement over naive O(n*m) substring search. It also enables efficient solutions to problems like finding the longest repeated substring, longest common substring between multiple strings, and longest palindromic substring. Suffix trees are foundational in bioinformatics, where they power genome alignment and search tools that must repeatedly query enormous DNA or protein sequences, and in text processing and search engines for full-text indexing. Their main practical drawback is memory overhead: even with linear asymptotic space, the constant factor is large (suffix trees commonly require 10-20 bytes per input character in practice), which has driven adoption of the more memory-efficient suffix array as a common substitute in production systems, often paired with an auxiliary LCP (longest common prefix) array to recover much of the suffix tree's query power.
Key Concepts
- Compressed trie representing all suffixes of a string
- Built in O(n) linear time via Ukkonen's, Weiner's, or McCreight's algorithms
- Stored in O(n) space despite implicitly representing O(n^2) suffix characters
- Supports substring search in O(m) time independent of text length
- Enables efficient longest-repeated-substring and longest-common-substring queries
- Powers genome and DNA sequence alignment tools in bioinformatics
- Higher memory overhead in practice than the more compact suffix array
- Foundational structure behind many full-text search and indexing systems