Lesson 9 · Advanced structures and algorithms

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.

Every Suffix, Sharing Prefixes

A suffix tree is a trie containing every suffix of a string, compressed so that any path without a branch becomes a single edge. For a text of length n there are n suffixes, and indexing all of them at once is what makes the structure powerful: any substring of the text is a prefix of some suffix, so a query about substrings becomes a walk from the root.

The uncompressed version — a suffix trie — makes the idea clear but is unusable. Storing all suffixes character by character takes O(n²) nodes, which for a one-megabyte text is a trillion nodes. The compression is not an optimisation; it is what makes the structure exist at all.

Path compression collapses every chain of single-child nodes into one edge. The consequence is a hard bound: a compressed tree has exactly n leaves, one per suffix, and every internal node has at least two children, so there are fewer than n internal nodes and therefore fewer than 2n nodes total.

The second half of the trick is that edges do not store the substrings they represent. Storing them would reintroduce the O(n²) space. Instead each edge holds a pair of indices into the original text, a start and an end, so an edge of any length costs two integers. The text must be kept alongside the tree, and the structure is O(n) in space.

A terminal character — conventionally $, chosen to appear nowhere else — is appended to the text before construction. Without it a suffix that is a prefix of another suffix ends partway along an edge rather than at a leaf, and the one-leaf-per-suffix property fails. In banana, the suffix na is a prefix of nana; appending $ forces every suffix to end at its own leaf.

Every substring is a prefix of some suffix — one structure indexes all
An uncompressed suffix trie is O(n²) and unusable
Compression gives n leaves and under 2n nodes total
Edges store index pairs, not characters, keeping space O(n)

Searching in Time Independent of the Text

To test whether a pattern of length m occurs in the text, walk down from the root matching the pattern's characters against the edge labels. If the walk consumes the whole pattern, the pattern occurs; if it hits a mismatch or runs out of edges, it does not.

The cost is O(m) — proportional to the pattern, with no dependence on the length of the text at all. Searching a hundred-character pattern costs the same in a one-kilobyte text as in a one-gigabyte one. That is the property no scanning algorithm can offer: KMP and Rabin–Karp are O(n + m) per search because they must traverse the text.

The distinction is about where the work is paid. A suffix tree spends O(n) once to build, then answers each query in O(m). KMP spends O(m) preprocessing per pattern and O(n) scanning per search. Search a text repeatedly and the tree wins decisively; search it once and building the tree is wasted effort.

Counting occurrences follows immediately. After the walk ends at some node, every leaf beneath it corresponds to one position where the pattern occurs, so the answer is the number of leaves in that subtree — precomputable in one pass so the count itself is O(1). The positions themselves are read from those leaves in O(k) for k occurrences.

The same structure answers questions that scanning algorithms handle poorly. The longest repeated substring is the deepest internal node, since an internal node means the path above it occurs in at least two places. The longest common substring of two texts is found by building the tree over both, concatenated with distinct separators, and finding the deepest node with leaves from each. Both are single traversals of a structure already built.

Suffix tree against the scanning algorithms
	Preprocess	Per search	Best for
Suffix tree	O(n) on the text	O(m)	Many patterns, one fixed text
KMP	O(m) on the pattern	O(n)	One pattern, streaming text
Rabin–Karp	O(m)	O(n) expected	Many patterns at once
Naive scan	None	O(n·m)	Tiny inputs only

Matching walks the pattern down from the root — O(m)
Cost is independent of the text length, unlike KMP or Rabin–Karp
Occurrence count is the leaf count of the subtree reached
Longest repeated substring is the deepest internal node

Ukkonen's Linear-Time Construction

Building the tree naively — inserting each of the n suffixes one at a time — costs O(n²). Ukkonen's algorithm achieves O(n) and is widely considered one of the harder standard algorithms to implement correctly, so understanding what it does matters more than reproducing it.

It is online: it processes the text one character at a time, and after each character the structure is a valid suffix tree of the prefix read so far. Three ideas make the linear bound work.

Implicit extension via a global end. When a new character arrives, every existing leaf edge must be extended by it. Rather than touching each leaf — which alone would be O(n) per character — leaf edges store their end as a shared pointer to a global variable. Incrementing that one variable extends every leaf simultaneously in O(1).

Suffix links. After splitting an edge to insert the suffix starting at position i, the algorithm must next work on the suffix starting at i+1. A suffix link from a node representing xα to the node representing α lets it jump there directly instead of descending from the root, which is what removes the repeated root-to-node walks.

Skipping resolved work. Once a suffix has been explicitly inserted, later phases need not revisit it; the algorithm tracks how far it has progressed and resumes rather than restarting. The total work across all phases telescopes to O(n) even though individual phases vary.

The alternative worth knowing is McCreight's algorithm, which also achieves O(n) but builds offline, requiring the whole text up front. It is often described as easier to follow, while Ukkonen's online property is what suits streaming input.

Naive insertion is O(n²); Ukkonen achieves O(n)
Online — valid for every prefix as characters arrive
A shared global end extends all leaf edges in O(1)
Suffix links skip the re-descent from the root

Key reference

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 aw to the internal node representing w. 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.

Implementation

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')

#include <iostream>
#include <map>
using namespace std;
struct SuffixTreeNode {
    map<char, SuffixTreeNode*> children;
    int start = -1, end = -1;
    // In Ukkonen's, we use indices [start, end]
};
int main() {
    // Edges store start/end index instead of characters
    SuffixTreeNode* root = new SuffixTreeNode();
    root->start = 0;
    root->end = 5;
    cout << "Tree Compressed\n";
}

import java.util.*;
public class Main {
    static class SuffixTreeNode {
        Map<Character, SuffixTreeNode> children = new HashMap<>();
        int start, end;
        // Edges represent compressed string indices
    }
    public static void main(String[] args) {
        SuffixTreeNode root = new SuffixTreeNode();
        root.start = 0;
        root.end = 5;
        System.out.println("Tree Compressed");
    }
}

Watch it run

Step through it

Running on suffixes of the displayed text

Output

Read all 11 Steps

The string Take 'banana$'. A suffix tree stores every suffix of the string in one compressed tree.
All suffixes There are 7 suffixes: banana$, anana$, nana$, ana$, na$, a$, $. Storing them separately would cost O(n²) characters.
Insert a-branch Suffixes starting with 'a' share their first character, so they share one edge out of the root.
Insert na-branch Suffixes starting with 'na' share a two-character edge. Edges hold substrings, not single letters — that is the compression.
Split under a Below 'a' the suffixes diverge into 'na$' and '$'. Two children.
Split under na 'na' likewise splits into 'na$' and '$'.
Linear size Because each edge stores a substring rather than a character, the whole tree is O(n) nodes even though it encodes O(n²) characters of suffixes.
Search 'nan' To test whether 'nan' occurs, walk from the root matching characters along the edges.
Continue 'na' matched the first edge. The next character 'n' continues into the child edge 'na$'.
Found All of 'nan' was matched, so it occurs in the string. Substring search costs O(m) — the pattern's length, independent of the text.
What it buys Every leaf is one suffix, so counting occurrences means counting leaves below the match point. That is why suffix trees answer pattern queries so cheaply.

Why Suffix Arrays Usually Win

Despite the elegance, suffix trees are comparatively rare in production, and the reason is the gap between O(n) space and how much space.

A suffix tree node carries child pointers, a suffix link, and edge indices. With an alphabet of size σ, child storage is either an array of σ pointers per node — fast but enormous — or a hash map, which is smaller but slower and less cache-friendly. Realistic implementations consume 10 to 20 bytes per input character, so a one-gigabyte text needs 10 to 20 gigabytes of structure.

A suffix array stores the same information as a plain integer array of the n starting positions, sorted by the suffix each begins. That is 4 or 8 bytes per character — often twenty times smaller — and it is contiguous, so traversing it is cache-friendly in a way that pointer-chasing through a tree is not.

The cost is query time. Searching a suffix array means binary searching the sorted suffixes at O(m log n) rather than O(m). Pairing it with an LCP array, which records the longest common prefix between adjacent suffixes, brings that down to O(m + log n) and recovers most of what the tree offered.

So the practical rule: suffix arrays are the default, and suffix trees are chosen when the queries genuinely need tree structure — repeated substrings, generalised matching over several texts, or algorithms that traverse internal nodes directly. Bioinformatics tools such as read aligners, which index genomes once and query them billions of times, are where the tree's constant factor is worth paying. Even there, compressed indexes like the FM-index and suffix automata have displaced both in many applications.

Suffix tree versus suffix array on the same text
	Suffix tree	Suffix array
Space	10–20 bytes per character	4–8 bytes per character
Search	O(m)	O(m log n), or O(m + log n) with LCP
Construction	O(n), hard to implement	O(n log n) simply, O(n) with effort
Locality	Pointer chasing	Contiguous, cache-friendly
Choose when	Structural queries on internal nodes	Almost everything else

O(n) space hides a 10–20× constant factor
Suffix arrays store the same information far more compactly
An LCP array recovers most of the query speed
Reach for the tree only when tree structure itself is needed