StringsAlgorithmaka compressed suffix trie, Ukkonen's algorithm, generalized suffix tree

Suffix Tree

A compressed trie of all suffixes of a string; answers substring search in O(m), longest repeat and distinct-substring counts directly from its structure.

Pattern: Trie Practice (2)

Progress

Overview

A suffix tree of s (usually with a unique terminator $ appended) is a compressed Trie containing every suffix of s$. Each edge is labelled with a substring of s, stored as an index pair (start, end), internal nodes have at least two children, and each of the n + 1 leaves corresponds to one suffix. The tree has at most 2n + 1 nodes and therefore O(n) size even though the suffixes total O(n²) characters.

It is the most powerful of the classic string indexes: a pattern p occurs in s iff walking p from the root succeeds, in O(m) time; the leaves below that point are all occurrences; the deepest internal node (by string depth) is the longest repeated substring; the number of distinct substrings is the sum of all edge-label lengths; and a generalized suffix tree of several strings yields their longest common substring by finding the deepest node with leaves from every string. Ukkonen's algorithm builds the tree online in O(n).

suffixescompressed trieUkkonenO(m) searchlinear construction

Intuition

A mental model before the formal terms.

Start with a trie of all suffixes: every substring of s corresponds to a path from the root. That trie can have Θ(n²) nodes, but most of them are chains with a single child. Squash every such chain into one edge, and instead of copying the letters store "characters start to end of s". That squashed trie is the suffix tree.

The naive way to build it is to insert the suffixes one by one, splitting an edge whenever a new suffix diverges in the middle of it: O(n²). Ukkonen's insight is to insert the string character by character, keeping every leaf edge "open" (its end is a global pointer that grows for free), remembering an active point where the next insertion happens, and adding suffix links between internal nodes so that after inserting a suffix starting at i the algorithm can jump to where the suffix starting at i + 1 needs work without walking from the root. Amortised, each character costs O(1).

How it works

Append a terminator $ that occurs nowhere else so that no suffix is a prefix of another; then every suffix ends at its own leaf.
Naive construction: for each suffix s[i..], walk from the root matching characters along edges. If the walk ends inside an edge, split it at that point into an internal node; then hang a new leaf edge for the remaining unmatched part of the suffix.
Ukkonen (linear): process s[0..i] for i = 0..n. Leaf edges end at a global end pointer, so extending all existing suffixes by one character is implicit. Only the suffixes that are not yet represented need explicit work; the active point tracks where they start, and suffix links move the active point from the suffix starting at j to the one starting at j + 1 in amortised O(1).
Query contains(p): from the root follow the child whose edge begins with p[0], compare along the edge, continue with the next edge; success iff all of p is consumed. Collect the leaves below to enumerate occurrences.
Distinct substrings: sum of edge lengths over the tree of s$, minus the n + 1 substrings that contain $ (one per leaf).

Why it works

Every substring of s is a prefix of some suffix, and every suffix is a root-to-leaf path, so the set of root-to-point paths in the tree is exactly the set of substrings. Walking p visits at most m characters, hence O(m) membership regardless of n.

The tree is small because the terminator makes all n + 1 suffixes end at distinct leaves, and each internal node has at least two children; a tree with n + 1 leaves and branching internal nodes has at most n internal nodes.

Ukkonen's O(n) bound comes from two amortisation arguments: the number of explicit insertions equals the number of nodes created, which is O(n); and the walk-down after following a suffix link uses the "skip/count" trick (jump whole edges by comparing lengths, not characters), so its total cost is bounded by the total decrease in active-point depth, again O(n).

Recognition

How to tell a problem wants this.

A problem needs O(m) substring queries independent of the text length, or online construction as characters arrive.
Longest repeated substring, longest common substring of multiple strings, number of distinct substrings, longest palindrome (via a generalized tree of s and reverse(s)).
The interviewer names "suffix tree" as a follow-up after a Suffix Array or Rolling Hash (Polynomial Hashing) solution.

“prefix” → Trie

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1s = s + "$"; root = empty node
2for i in 0 .. n:            # insert suffix s[i..]
3  node = root, pos = i
4  loop:
5    if s[pos] has no edge from node: add leaf edge (pos, n+1); break
6    edge = node.child[s[pos]]; walk k chars while they match
7    if k == len(edge): node = edge.child; pos += k; continue
8    split edge at k into mid; hang leaf edge (pos+k, n+1) on mid; break
9contains(p): walk p from root along edge labels; true iff fully consumed

Implementations

1class SuffixTree:
2    """A compressed trie of every suffix: each edge carries a SUBSTRING
3    (stored as [start, end) into the text), not a single character, so the
4    tree has at most 2n nodes. Built by inserting suffixes one at a time and
5    splitting edges — O(n^2) worst case, the honest simple construction;
6    Ukkonen's algorithm does the same job in O(n)."""
7 
81 · An edge is a text range; a node is a dict from first character to child
9    def __init__(self, s: str) -> None:
102 · Append a terminator so no suffix is a prefix of another
11        self.text = s + "\u0001"
12        self.start: list[int] = [0]
13        self.end: list[int] = [0]
14        self.children: list[dict[str, int]] = [{}]
15        self.suffix_index: list[int] = [-1]
16        for i in range(len(self.text)):
17            self._insert_suffix(i)
18 
19    def _add_node(self, start: int, end: int) -> int:
20        self.start.append(start)
21        self.end.append(end)
22        self.children.append({})
23        self.suffix_index.append(-1)
24        return len(self.start) - 1
25 
263 · Walk down matching characters; split the edge where they diverge
27    def _insert_suffix(self, suffix_start: int) -> None:
28        text = self.text
29        n = len(text)
30        cur = 0
31        i = suffix_start
32        while i < n:
33            child = self.children[cur].get(text[i])
34            if child is None:
35                leaf = self._add_node(i, n)
36                self.suffix_index[leaf] = suffix_start
37                self.children[cur][text[i]] = leaf
38                return
39            j = self.start[child]
40            while j < self.end[child] and i < n and text[j] == text[i]:
41                j += 1
42                i += 1
43            if j == self.end[child]:
44                cur = child  # consumed the whole edge, descend
45                continue
464 · Divergence mid-edge: insert an internal node at the split point
47            split = self._add_node(self.start[child], j)
48            self.start[child] = j
49            self.children[split][text[j]] = child
50            self.children[cur][text[self.start[split]]] = split
51            leaf = self._add_node(i, n)
52            self.suffix_index[leaf] = suffix_start
53            self.children[split][text[i]] = leaf
54            return
55 
565 · Substring search is a single root-to-somewhere walk, O(pattern)
57    def contains(self, pattern: str) -> bool:
58        text = self.text
59        cur = 0
60        i = 0
61        while i < len(pattern):
62            child = self.children[cur].get(pattern[i])
63            if child is None:
64                return False
65            j = self.start[child]
66            while j < self.end[child] and i < len(pattern):
67                if text[j] != pattern[i]:
68                    return False
69                j += 1
70                i += 1
71            cur = child
72        return True

Walkthrough

This version uses parallel lists (start, end, children, suffix_index) rather than a node class, which avoids one Python object per node — the same choice as the Aho-Corasick implementation.
self.children[cur].get(text[i]) returns None for a missing child, and is None is the correct test: node index 0 is the root and is falsy.
text = self.text and n = len(text) are hoisted into locals at the top of _insert_suffix, removing an attribute lookup from every iteration of the inner loop.
The split assigns self.start[child] = j, so the existing child retains only the second half of its former edge.
The "\u0001" terminator is a control character that will not occur in normal text, forcing every suffix to end at a leaf.

Complexity (this implementation)

time O(n^2) worst case to build, O(m) per substring query · space O(n) nodes

For substring queries specifically, Python's built-in in operator is C-implemented and will beat this tree for any single query — the tree pays off for many queries against one fixed text.

Language notes

dict.get(k) returning None versus a valid node index of 0 is why is None appears rather than a truthiness check.
Parallel lists are noticeably lighter than a class per node in CPython; @dataclass(slots=True) is the middle ground if readability matters more.
Python strings iterate and index by code point, so no surrogate-pair handling is needed, unlike JavaScript.
pysuffixarray and suffix-trees exist on PyPI, but a suffix *array* plus LCP (see the neighbouring topic) is usually the better engineering choice.

Common mistakes in this language

Writing if not child: instead of if child is None:, which treats the root as absent.
Rebuilding the tree for each query when the text is fixed — the construction cost is the whole investment.
Storing edge labels as substrings, which makes memory O(n^2) for a highly repetitive text.

Language differences that matter here

The falsy-zero trap recurs here in all three dynamic languages: Map.get returning undefined in JS/TS and dict.get returning None in Python must be distinguished from node index 0, and only TypeScript makes the check mandatory.
Node storage: C++ and JS/TS use records in an array; the Python version uses parallel lists to avoid per-node object overhead — an optimisation the other two do not need.
Character indexing: Python indexes by code point, C++ by byte, and JS/TS by UTF-16 unit — all three are internally consistent, but a suffix tree built in one will not agree with the other on non-BMP text.
Every language here would, in practice, be better served by a suffix array plus LCP (or a suffix automaton), and only Python and C++ have mature library options for either.

Complexity

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(n · σ)

Ukkonen builds in O(n) for a fixed alphabet (O(n log σ) with ordered maps); the naive insertion shown is O(n²). Search is O(m); the constant factor in space is large (roughly 10–20 words per character).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Substring queries in O(m) independent of n, or many different query types on one text.
Longest common substring of several strings (generalized suffix tree).
Online construction while the text is still streaming in (Ukkonen).
Bioinformatics-scale exact matching where O(m) lookups with occurrence lists matter.

Avoid it when

Memory-constrained settings — a Suffix Array plus LCP gives most of the same answers with a fraction of the space.
Anything an interview expects you to code from scratch in 30 minutes; Ukkonen is notoriously fiddly. Offer it as the theoretical optimum, implement Suffix Array or Rolling Hash (Polynomial Hashing).
Single-pattern or multi-pattern search where Knuth–Morris–Pratt (KMP) or Aho–Corasick apply.

Alternatives

Suffix Array Rolling Hash (Polynomial Hashing)Aho–Corasick Trie

Common mistakes

Omitting the terminator $, so a suffix that is a prefix of another (e.g. "a" in "aa") ends in the middle of an edge and has no leaf.
Storing edge labels as substrings instead of index pairs, which brings the size back to O(n²).
In Ukkonen, forgetting to set the suffix link of the previously created internal node in the same phase, or not applying the skip/count walk-down after following a link.
Counting distinct substrings without subtracting the n + 1 substrings that contain the terminator.

Interview patterns

Longest repeated substring: deepest internal node by string depth.
Longest common substring of two strings: deepest node whose subtree has leaves from both.
Count distinct substrings: sum of edge lengths.
Longest palindromic substring via a generalized tree of s and reverse(s) plus LCA queries (Manacher is far simpler in practice).

Mock interviews

Implement Trie (Prefix Tree)Intermediate

Example problems

Longest Palindromic Substringmedium Find the Index of the First Occurrenceeasy