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
Use Cases
Frequently Asked Questions
From the Blog
What Is a Decision Tree in Machine Learning
A decision tree predicts by asking a series of yes/no questions about your data, splitting it step by step until it reaches an answer. It is simple, visual, and easy to read.
Read More AI & TechnologyReAct, Chain-of-Thought and Tree of Thoughts Compared
Chain-of-thought adds reasoning tokens, ReAct interleaves reasoning with tool calls, and Tree of Thoughts explores multiple reasoning branches with backtracking. This article compares the three on cost, latency and the problem shapes where each genuinely improves accuracy, and shows how to escalate between them so that easy inputs never pay for the expensive scaffold.
Read More ProgrammingTrees in Programming: A Complete Beginner's Guide
A tree is a hierarchical data structure of nodes linked from a single root. Learn how trees work, key types like binary search trees, and how to traverse them.
Read More AI & TechnologyWhat Is a Random Forest Explained Simply
A Random Forest is a team of decision trees that vote on the answer. Randomness makes each tree different, so their combined prediction is accurate and hard to overfit.
Read More