Suffix Trees (Ukkonen Intuition)
Why this exists
The suffix array lesson sorted all suffixes of a text, so that any pattern query became a binary search. That costs per query for a pattern of length in a text of length . Can we get , independent of , like walking down a trie?
Yes: put all the suffixes of the text into a trie. Every substring is a prefix of some suffix, so every substring is a path from the root. Checking whether occurs is walking letter by letter from the root. That structure is the suffix trie. Its problem is size: a text of length has up to about distinct substrings, so the trie can have about nodes. For random DNA of length 1,000 we measured 497,356 trie nodes.
The fix is the same as for any trie with long chains: compress every chain of single-child nodes into one edge labelled with a string. The result is the suffix tree. It has at most nodes, and if edge labels are stored as two indices into the text (not as copied strings), it takes space. The same random 1,000-letter DNA string gives 1,611 nodes instead of 497,356.
The suffix tree is one of the most celebrated data structures in stringology. Peter Weiner built it in linear time in 1973 ("Linear pattern matching algorithms", 14th IEEE Symposium on Switching and Automata Theory); Donald Knuth reportedly called it "the algorithm of the year". Edward McCreight gave a simpler, more space-efficient linear construction in 1976 (Journal of the ACM 23(2)). Esko Ukkonen gave the version everybody teaches, which builds the tree online, one character at a time, left to right ("On-line construction of suffix trees", Algorithmica 14(3), 1995). Martin Farach (FOCS 1997) showed linear-time construction for integer alphabets.
Dan Gusfield's textbook (Algorithms on Strings, Trees, and Sequences, 1997) lists dozens of problems that a suffix tree solves in linear time. In practice, as we will see, suffix arrays and suffix automata have taken over many of those jobs because they are smaller and simpler. But the suffix tree is the picture behind all of them: an LCP array is a suffix tree's depths read in order, and the suffix automaton is (almost) the suffix tree of the reversed string. Understanding the tree makes the other two make sense.
This lesson is about intuition first: what the tree looks like, why it is small, how the naive build works, and the four ideas that make Ukkonen's algorithm linear. You get a full, tested Python Ukkonen and a four-language naive builder with a substring API.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| Fixed text, many "does P occur / how many times" queries, need each | Suffix tree (or suffix automaton) |
| "longest repeated substring" | Deepest internal node (by string depth) |
| "longest common substring of strings" | Generalized suffix tree, deepest node whose subtree contains all colours |
| "number of distinct substrings" | Sum of edge lengths (excluding the terminator) |
| "for every position of T, longest prefix that occurs in S" (matching statistics) | Suffix tree of S + suffix links, walk T |
| "shortest substring that occurs exactly once / does not occur" | Leaves and their parent depths |
| Text arrives one character at a time and queries interleave | Ukkonen (online), or a suffix automaton |
| Contest problem with suffix-tree flavour, tight time | Usually suffix automaton or suffix array + LCP is easier to code |
The meta-trigger: you would draw all suffixes as paths from one root and ask questions about where they branch. Branch points are repeated substrings; leaves are suffixes; subtree sizes are occurrence counts.
Intuition & first principles
From suffix trie to suffix tree
Take abab and add a terminator $ (explained in a moment): abab$. Its five suffixes are abab$, bab$, ab$, b$, $. Insert them all into a trie:
flowchart TD
R(("root")) -- a --> A(("a"))
A -- b --> AB(("ab"))
AB -- a --> ABA(("aba"))
ABA -- b --> ABAB(("abab"))
ABAB -- "$" --> L0["leaf 0"]
AB -- "$" --> L2["leaf 2"]
R -- b --> B(("b"))
B -- a --> BA(("ba"))
BA -- b --> BAB(("bab"))
BAB -- "$" --> L1["leaf 1"]
B -- "$" --> L3["leaf 3"]
R -- "$" --> L4["leaf 4"]
That is 13 nodes. Most of them have exactly one child: a → ab is forced, ab → aba → abab → leaf is a chain. Compress every chain into one edge with a string label:
flowchart TD
R(("root")) -- "ab" --> AB(("ab"))
AB -- "ab$" --> L0["leaf 0"]
AB -- "$" --> L2["leaf 2"]
R -- "b" --> B(("b"))
B -- "ab$" --> L1["leaf 1"]
B -- "$" --> L3["leaf 3"]
R -- "$" --> L4["leaf 4"]
Eight nodes: the root, two internal nodes (ab and b, the places where suffixes disagree), and five leaves (one per suffix, labelled with the suffix's start index). That is the suffix tree.
Read it:
- Does
baoccur? Walk from the root:btakes the edgeb, thenamatches the first letter of edgeab$. Yes. - How many times does
aboccur? Walkab, you land on nodeab, which has two leaves below it (0 and 2). Two occurrences, at positions 0 and 2. - Longest repeated substring? The internal node with the longest path from the root:
ab(length 2). Internal nodes are exactly the substrings that occur at least twice and are followed by different letters.
Vocabulary
- The string depth of a node is the length of the string spelled from the root to it. Node
abhas string depth 2. - A locus of a string is the place in the tree where the path for ends: either at a node or in the middle of an edge.
- An internal node has at least two children; a leaf has none. Every non-root node is entered by exactly one edge.
- A suffix link goes from an internal node spelling (one letter followed by a string ) to the node spelling . In the picture above,
ab→b, andb→ root. Suffix links are Ukkonen's main tool; the same idea powers the failure links of Aho–Corasick.
Why the $ terminator
Build the tree of abab without $. The suffixes are abab, bab, ab, b. But ab is a prefix of abab and b is a prefix of bab. So the paths for ab and b end in the middle of an edge, not at leaves. The tree would have only 2 leaves for 4 suffixes, and "count leaves below a node" would undercount occurrences.
Adding a character that occurs nowhere else forces every suffix to differ from every other at some point (at its $, if not earlier). So no suffix is a prefix of another, every suffix ends at its own leaf, and there are exactly leaves for the suffixes of . The tree without the terminator is called an implicit suffix tree; it appears naturally in the middle of Ukkonen's algorithm, and the final $ turns it into a true (explicit) one.
The suffix tree of banana$
flowchart TD
R(("root")) -- "a" --> A(("a"))
R -- "banana$" --> L0["0"]
R -- "na" --> N(("na"))
R -- "$" --> L6["6"]
A -- "$" --> L5["5"]
A -- "na" --> ANA(("ana"))
ANA -- "$" --> L3["3"]
ANA -- "na$" --> L1["1"]
N -- "$" --> L4["4"]
N -- "na$" --> L2["2"]
Seven leaves (suffixes 0–6), three internal nodes (a, ana, na) plus the root: 11 nodes, against 23 in the suffix trie. Compare it with the suffix array of banana, : read the leaves left to right with children in alphabetical order (and $ first) and you get , the suffix array of banana$. The string depths of the branching nodes between consecutive leaves are the LCP values . A suffix array plus its LCP array is a suffix tree flattened into a list.
Mechanics
Why the tree has size
Let be the length of .
- Leaves. Each suffix ends at its own leaf (because of
$), and every leaf is the end of some suffix. Exactly leaves. - Internal nodes. Every internal node except possibly the root has at least two children: a node with one child would have been compressed into its edge. (The root has at least two children too whenever : suffix
$and suffix 0 start with different letters.) In any rooted tree where every internal node has at least 2 children, the number of internal nodes is at most (leaves − 1). Why: count edges two ways. Edges nodes , and edges (each internal node has child edges). So , that is, . So at most internal nodes. - Total at most nodes and edges.
- Edge labels. An edge label is a substring of , so store it as a pair of indices . Two integers per edge, whatever the label length.
So the tree has nodes, edges, and words of memory, even though it encodes all substrings. The measured worst case is aaaa…a$: leaves and internal nodes (each a for is a node with children a… and $). With Ukkonen produced exactly 100,001 leaves and 100,000 internal nodes counting the root.
words, not small
"Linear space" hides a big constant. Each node needs its edge's start and end, a way to find children (array, hash map or sibling list), a suffix link and often a leaf index. Stefan Kurtz's careful engineering study ("Reducing the space requirement of suffix trees", Software: Practice and Experience 29(13), 1999) got the best representation down to 20 bytes per input character in the worst case and 10.1 bytes on average over 42 test files; the same paper reports earlier implementations at roughly 18.8 to 22.4 bytes per character for real inputs. A plain suffix array is 4 bytes per character. A straightforward pointer-and-hash-map implementation (like the Python below) uses hundreds of bytes per character.
Naive construction: insert the suffixes one by one,
The obvious algorithm: start with a root, insert , then , and so on. To insert a suffix, walk down from the root comparing letters:
- If you fall off at a node (no child edge starts with the next letter), hang a new leaf there.
- If you fall off in the middle of an edge (the next letter on the edge differs), split the edge at that point: create a new internal node, make the old lower part of the edge one child and a new leaf the other.
- You never run out of suffix inside the tree, thanks to
$.
Inserting banana$ suffix by suffix:
| Insert | Walk | Action | Nodes after |
|---|---|---|---|
banana$ (0) | root has no b child | new leaf under root | 2 |
anana$ (1) | no a child | new leaf | 3 |
nana$ (2) | no n child | new leaf | 4 |
ana$ (3) | edge anana$: ana matches, then $ ≠ n | split after ana: node ana, children na$ (old, leaf 1) and $ (leaf 3) | 6 |
na$ (4) | edge nana$: na matches, then $ ≠ n | split after na: node na, children na$ (leaf 2) and $ (leaf 4) | 8 |
a$ (5) | edge ana: a matches, then $ ≠ n | split after a: node a, children na (to node ana) and $ (leaf 5) | 10 |
$ (6) | no $ child | new leaf | 11 |
Inserting suffix costs up to its length, , so the total is in the worst case (aaaa…a). On random text, suffixes fall off after about letters, so it is close to . Measured in Python: random DNA of length 100,000 builds naively in 0.21 s; all-a of length 5,000 takes 0.46 s and length 10,000 takes 1.85 s (quadratic: double , four times the time). Ukkonen builds all-a of length 100,000 in 0.12 s.
Ukkonen's idea 1: build online, prefix by prefix
Naive construction inserts suffixes of the whole text. Ukkonen instead processes the text left to right and maintains, after reading , the (implicit) suffix tree of that prefix. Each step is a phase: phase adds the character .
What must phase do? The suffixes of are the suffixes of , each extended by , plus the new one-letter suffix . So phase has extensions: for each , make sure the string is in the tree, by extending the path for with . Done naively that is extensions each costing walking: in total. Four ideas collapse it to .
The three extension rules
When extension looks at the end of the path :
| Rule | Situation at the end of | Action | Cost |
|---|---|---|---|
| 1 | ends at a leaf | Append to that leaf's edge | , and in fact free (idea 2) |
| 2 | ends at a node or inside an edge, and no path continues with | Add a new leaf for ; if inside an edge, split it to create an internal node | once we are there |
| 3 | A path continuing with already exists | Do nothing: is already in the tree (implicitly) | , and it ends the phase (idea 3) |
Ukkonen's idea 2: "once a leaf, always a leaf"
A leaf created for the suffix starting at stays a leaf forever: nothing is ever hung below a leaf, because Rule 2 only acts at the end of a path that has no continuation, and a leaf's edge always ends at the current end of the text. In every later phase, Rule 1 applies to it: its edge grows by one letter.
So do not touch leaves at all. Give every leaf edge the label , where END is a single shared global variable meaning "the current end of the text". Setting END = i at the start of phase performs all Rule 1 extensions at once in . In the Python code below, every leaf points to the same one-element list leaf_end.
Consequence: the extensions that are leaves form a prefix of the work, and they are done for free. If the previous phase created leaves for every up to some , this phase only needs to do explicit work from onwards.
Ukkonen's idea 3: Rule 3 is a "showstopper"
If extension finds that is already in the tree (Rule 3), then every shorter suffix with is also already there: it is a suffix of , and if a string occurs in the text so far, so do all its suffixes, all of which are paths in the tree. So the phase can stop right there. The remaining suffixes are carried into the next phase as "pending".
Ukkonen's algorithm keeps a counter, the remainder: how many suffixes still need to be explicitly inserted. Each phase adds 1 (the new letter's suffix); each Rule 2 insertion subtracts 1; Rule 3 ends the phase with the remainder unchanged.
Ukkonen's idea 4: the active point and suffix links
The pending suffixes are always the shortest suffixes of the current prefix, so only the longest pending one needs to be tracked: the others are its suffixes. Its locus in the tree is the active point, stored as a triple:
- active node: the node we are below (often the root),
- active edge: which child edge we are on (stored as an index into , whose letter picks the edge),
- active length: how many letters down that edge.
After a Rule 2 insertion at the active point for the suffix , the next pending suffix is . Where is 's locus? If the active node spells (with the rest of the path, , given by active edge and length), then , and its locus is " below the node spelling ". The suffix link of the active node points exactly to that node. So:
- If the active node is an internal node, follow its suffix link; keep the active edge and length.
- If the active node is the root, there is no link to follow; instead drop the first letter by hand: active length decreases by 1 and the active edge moves one position to the right.
Suffix links are created as we go: when a phase creates several internal nodes in a row (one per Rule 2 split), each one's suffix link points to the next one created (or to the node where the next extension happened). A lemma guarantees the target exists by the end of the extension (see Correctness).
One more trick, skip/count (also called "walk down"): when the active length is at least the length of the active edge, jump over the whole edge in (subtract its length, move the active node down) instead of comparing its letters. We know the letters match, because the pending suffix is known to be in the tree.
flowchart TD
P["Phase i: END = i, remainder += 1"] --> W{"active length at least edge length?"}
W -- yes --> SK["skip/count: move active node down"]
SK --> W
W -- no --> Q{"next letter c already there?"}
Q -- "yes: Rule 3" --> R3["active length += 1, set pending suffix link, END PHASE"]
Q -- "no: Rule 2" --> R2["new leaf, split edge if inside one, link previous new node"]
R2 --> D["remainder -= 1"]
D --> M{"active node is root?"}
M -- yes --> RT["active length -= 1, active edge moves right"]
M -- no --> SL["follow suffix link"]
RT --> C{"remainder > 0?"}
SL --> C
C -- yes --> W
C -- no --> NP["next phase"]
Step-by-step: Ukkonen on abcabxabcd$
This is the classic example (it shows Rule 3, walk-down, splits and suffix links in eleven phases). The table was printed by an instrumented run of the Python code below. "AP" is the active point after the phase, written (node, edge letter, length); root, -, 0 means "at the root".
| Phase | Char | What happens | Remainder after | AP after |
|---|---|---|---|---|
| 0 | a | Rule 2: leaf a… (suffix 0) under root | 0 | root, -, 0 |
| 1 | b | END moves: leaf 0 now reads ab (Rule 1 for free). Rule 2: leaf b… (suffix 1) | 0 | root, -, 0 |
| 2 | c | Leaves grow to abc, bc. Rule 2: leaf c… (suffix 2) | 0 | root, -, 0 |
| 3 | a | a already starts edge abca: Rule 3, phase ends. Pending: a | 1 | root, a, 1 |
| 4 | b | ab already on the same edge: Rule 3. Pending: ab, b | 2 | root, a, 2 |
| 5 | x | Pending abx, bx, x. At (root, a, 2) the edge says c, not x: split after ab, new internal node ab, leaf x… (suffix 3). At the root: active length 2 → 1, edge moves to b. Split after b, node b, leaf (suffix 4); suffix link ab → b. Length 1 → 0: Rule 2 at root, leaf x… (suffix 5) | 0 | root, -, 0 |
| 6 | a | Rule 3 on edge ab | 1 | root, a, 1 |
| 7 | b | Rule 3: ab matches the whole edge into node ab | 2 | root, a, 2 |
| 8 | c | Walk down: active length 2 equals edge length 2, so the active node becomes ab, length 0. Then c already starts an edge below ab: Rule 3 | 3 | ab, c, 1 |
| 9 | d | Pending abcd, bcd, cd, d. Split below ab after c: node abc, leaf (suffix 6). Follow suffix link ab → b; split after c below b: node bc, leaf (suffix 7), link abc → bc. Follow link b → root; split after c: node c, leaf (suffix 8), link bc → c. At root, length 1 → 0: leaf d… (suffix 9), link c → root | 0 | root, -, 0 |
| 10 | $ | Rule 2: leaf $ (suffix 10). All 11 suffixes now end at leaves | 0 | root, -, 0 |
Phase 9 is the heart of the algorithm. Four pending suffixes are inserted, and each jump to the next one costs : follow a suffix link, keep the active edge and length. Without suffix links we would have to walk bc and c from the root again.
The final tree:
flowchart TD
R(("root")) -- "ab" --> AB(("ab"))
R -- "b" --> B(("b"))
R -- "c" --> C(("c"))
R -- "d$" --> L9["9"]
R -- "xabcd$" --> L5["5"]
R -- "$" --> L10["10"]
AB -- "c" --> ABC(("abc"))
AB -- "xabcd$" --> L3["3"]
ABC -- "abxabcd$" --> L0["0"]
ABC -- "d$" --> L6["6"]
B -- "c" --> BC(("bc"))
B -- "xabcd$" --> L4["4"]
BC -- "abxabcd$" --> L1["1"]
BC -- "d$" --> L7["7"]
C -- "abxabcd$" --> L2["2"]
C -- "d$" --> L8["8"]
AB -. "link" .-> B
ABC -. "link" .-> BC
BC -. "link" .-> C
Eleven leaves, six internal nodes including the root. Dotted arrows are suffix links (links to the root are omitted).
The ladder: brute force → better → optimal
| Rung | Method | Build time | Space | Why it improves |
|---|---|---|---|---|
| 1 | Suffix trie | nodes | Baseline: every substring is a path | |
| 2 | Naive compressed tree (insert suffixes) | worst, ~ on random text | Compression: nodes, index-pair labels | |
| 3 | Ukkonen without suffix links (rescan from root) | Online; leaves and Rule 3 cut most work | ||
| 4 | Ukkonen with suffix links + skip/count | for constant alphabet ( with sorted children) | Every extension is amortised | |
| 4' | Weiner (1973), McCreight (1976) | Same bound, offline (right-to-left / suffix-by-suffix) | ||
| 5 | Farach (1997) | for integer alphabets | Removes the alphabet factor; also via SA-IS + LCP |
A practical "rung 5" in many systems: build a suffix array with SA-IS and the LCP array with Kasai, both , and recover the tree's internal nodes from the LCP intervals with a stack. That is how enhanced suffix arrays simulate a suffix tree.
Correctness
Lemma 1: suffix links exist
If is an internal node, then is an internal node (or the root, when is empty) by the end of the next extension.
Why. is internal, so it has at least two children starting with different letters, say and : both and occur in the text. Then and also occur (drop the first letter), so the path for branches, and must be a node. In Ukkonen's algorithm, the only subtle case is when was just created in this phase by a split with a new leaf for letter : then the next extension handles , and either finds a node there already, or creates it by its own split (Rule 2), or finds already present (Rule 3), in which case 's locus is the active node itself. In each case the link can be set at that moment, which is what the code does.
We also tested this directly: for 5,000 random strings over alphabets of sizes 1–3, every internal node's suffix link points to the node spelling its path minus the first letter.
Lemma 2: the three rules preserve "the tree contains every suffix of the prefix"
Invariant: after phase , every suffix of is a path from the root (possibly ending inside an edge).
- Rule 1 extends leaf paths: the END trick appends to every leaf simultaneously.
- Rule 2 creates the missing path for .
- Rule 3 means already exists; and so do all its suffixes (idea 3), so stopping is safe.
- The pending suffixes are tracked exactly by the remainder and the active point, so none is forgotten: each is inserted in some later phase, at the latest when
$arrives, since$cannot already be in the tree and therefore every pending suffix hits Rule 2 in the last phase.
After the $ phase, the remainder is 0 and every suffix of ends at its own leaf. We checked the result exhaustively against the definition on 3,000 random strings in the code below (sorted root-to-leaf paths equal the sorted suffixes) and on another 5,000 in the suffix-link test.
Lemma 3: Ukkonen runs in (for a constant alphabet)
Count the work by type:
- Leaf extensions (Rule 1): per phase in total thanks to END. .
- Rule 2 insertions: each creates a leaf, and there are exactly leaves in the end and leaves are never deleted. .
- Rule 3 events: at most one per phase. .
- Moving between pending suffixes: one suffix-link hop or one root adjustment per Rule 2 insertion. .
- Skip/count jumps: each jump subtracts at least 1 from the active length. The active length only grows in Rule 3, by exactly 1, at most once per phase. So the total number of jumps is at most . .
Every step does work if finding a child by its first letter is (array of size or a hash map). Total . With balanced search trees for children it is .
That amortisation is the same flavour as KMP's staircase: a quantity (active length) that rises by at most one per step can only fall a bounded number of times.
Complexity
| Operation | Time | Notes |
|---|---|---|
| Build (Ukkonen, McCreight, Weiner) | for constant ; with sorted children | Online for Ukkonen |
| Build (naive) | worst, about on random text | Easy to code |
| "Does P occur?" | Walk from the root | |
| "How many times?" | after an pass storing leaf counts | Count leaves below the locus |
| "Where?" | List the leaves below the locus | |
| Distinct substrings | Sum of edge lengths minus terminators | |
| Longest repeated substring | Deepest internal node | |
| Space | words; ~10–20 bytes/char engineered (Kurtz 1999), much more naive | vs 4 bytes/char for a suffix array |
Measured with the Python Ukkonen below: 100,000 random DNA letters in about 0.10 s, 100,000 as in about 0.12 s (the worst case for naive construction is no harder for Ukkonen).
Implementation
Ukkonen's algorithm in Python (full)
This is a complete Ukkonen with suffix links, skip/count and the shared leaf end. It also offers contains, suffixes, count_nodes and distinct_substrings. The test at the bottom compares the tree with the definition (every root-to-leaf path is a suffix, and every suffix is a root-to-leaf path) on 3,000 random strings, plus substring counts and membership queries. It passes on Python 3.12. Children are stored in a dict, so for a constant alphabet each operation is expected .
class Node:
__slots__ = ("start", "end", "children", "link", "suffix")
def __init__(self, start: int, end: "list[int]") -> None:
self.start = start # edge INTO this node is s[start : end[0] + 1]
self.end = end # a one-element list, so all leaves can share it
self.children: dict[str, Node] = {}
self.link: "Node | None" = None # suffix link (internal nodes only)
self.suffix = -1 # leaves: start index of the suffix they spell
class SuffixTree:
"""Ukkonen's online construction, O(n) for a constant alphabet.
The text must end with a unique terminator (default '$') so that every
suffix ends at a leaf.
"""
def __init__(self, text: str, terminator: str = "$") -> None:
if terminator in text:
raise ValueError("terminator must not occur in text")
self.s = s = text + terminator
self.root = root = Node(-1, [-1])
root.link = root
leaf_end = [-1] # rule 1 for free: one shared end
active_node, active_edge, active_len = root, 0, 0
remainder = 0 # suffixes still to be inserted
for i, c in enumerate(s):
leaf_end[0] = i # every leaf grows by one ("once a leaf, always a leaf")
remainder += 1
last_internal: Node | None = None
while remainder > 0:
if active_len == 0:
active_edge = i
edge_char = s[active_edge]
child = active_node.children.get(edge_char)
if child is None:
# Rule 2 at a node: hang a new leaf directly off active_node.
leaf = Node(i, leaf_end)
leaf.suffix = i - remainder + 1
active_node.children[edge_char] = leaf
if last_internal is not None:
last_internal.link = active_node
last_internal = None
else:
edge_len = child.end[0] - child.start + 1
if active_len >= edge_len:
# Skip/count: jump over the whole edge without comparing.
active_edge += edge_len
active_len -= edge_len
active_node = child
continue
if s[child.start + active_len] == c:
# Rule 3: c is already there. Stop this phase (the "showstopper").
if last_internal is not None and active_node is not root:
last_internal.link = active_node
last_internal = None
active_len += 1
break
# Rule 2 inside an edge: split it, add a new leaf.
split = Node(child.start, [child.start + active_len - 1])
split.link = root
active_node.children[edge_char] = split
leaf = Node(i, leaf_end)
leaf.suffix = i - remainder + 1
split.children[c] = leaf
child.start += active_len
split.children[s[child.start]] = child
if last_internal is not None:
last_internal.link = split
last_internal = split
remainder -= 1
if active_node is root and active_len > 0:
active_len -= 1
active_edge = i - remainder + 1
elif active_node is not root:
active_node = active_node.link
self.n = len(s)
def edge(self, v: Node) -> str:
return self.s[v.start:v.end[0] + 1]
def contains(self, p: str) -> bool:
"""Is p a substring of the text? O(m) for a constant alphabet."""
v, k = self.root, 0
while k < len(p):
child = v.children.get(p[k])
if child is None:
return False
label = self.edge(child)
if p[k:k + len(label)] != label[:len(p) - k]:
return False
k += len(label)
v = child
return True
def suffixes(self) -> list[str]:
"""Every root-to-leaf path, i.e. every suffix of text + '$'."""
out, stack = [], [(self.root, "")]
while stack:
v, path = stack.pop()
if not v.children:
out.append(path)
for child in v.children.values():
stack.append((child, path + self.edge(child)))
return out
def count_nodes(self) -> tuple[int, int]:
leaves = internal = 0
stack = [self.root]
while stack:
v = stack.pop()
if v.children:
internal += 1
stack.extend(v.children.values())
else:
leaves += 1
return leaves, internal
def distinct_substrings(self) -> int:
"""Sum of edge lengths, not counting the terminator."""
total, stack = 0, list(self.root.children.values())
while stack:
v = stack.pop()
total += len(self.edge(v).rstrip(self.s[-1]))
stack.extend(v.children.values())
return total
if __name__ == "__main__":
import random
st = SuffixTree("banana")
assert sorted(st.suffixes()) == ["$", "a$", "ana$", "anana$", "banana$", "na$", "nana$"]
assert st.count_nodes() == (7, 4) # 7 leaves; root + 3 internal nodes
assert st.distinct_substrings() == 15
assert st.contains("nan") and not st.contains("nab")
rng = random.Random(7)
for _ in range(3000): # compare with the definition
t = "".join(rng.choice("abc"[:rng.randint(1, 3)]) for _ in range(rng.randint(0, 30)))
st = SuffixTree(t)
s = t + "$"
assert sorted(st.suffixes()) == sorted(s[i:] for i in range(len(s))), t
subs = {t[i:j] for i in range(len(t)) for j in range(i + 1, len(t) + 1)}
assert st.distinct_substrings() == len(subs), t
leaves, internal = st.count_nodes()
assert leaves == len(s) and internal <= len(s) # internal count includes the root
p = "".join(rng.choice("abc") for _ in range(rng.randint(1, 5)))
assert st.contains(p) == (p in t)
print("ukkonen ok")
Why only Python for Ukkonen
A correct Ukkonen is about 70 lines with many subtle invariants (when to set a suffix link, when to move the active edge, the walk-down continue). Translating it into four languages would quadruple the places for a bug without teaching anything new. The four-language code below instead implements the naive compressed suffix tree with the same query API (contains, count, distinct substrings, longest repeated substring). It is what you would actually write under time pressure for up to a few thousand, and it is a perfect brute-force oracle for testing a fast implementation. For large inputs in Java, C++ or TypeScript, a suffix array + LCP or a suffix automaton is the usual choice anyway.
Naive compressed suffix tree in four languages
Each node owns the edge that enters it, stored as indices start[v]..end[v] into ; node 0 is the root. A post-order pass stores leaves-below and string depth for every node. Every snippet checks banana by hand-verified values (11 nodes, ana occurs twice, 15 distinct substrings, longest repeat ana) and then compares against brute force on 2,000 random strings over {a, b}. All four were run: Python 3.12, Java 21, g++ (-std=c++17 -O2 -Wall), Node 24 (type stripping).
class NaiveSuffixTree:
"""Compressed suffix tree built by inserting suffixes one by one: O(n^2) time, O(n) nodes."""
def __init__(self, text: str, terminator: str = "$") -> None:
assert terminator not in text
self.s = s = text + terminator
n = len(s)
# Node v owns the edge s[start[v]:end[v]] that leads INTO it. Node 0 is the root.
self.start, self.end, self.kids, self.suffix = [0], [0], [{}], [-1]
for i in range(n): # insert suffix s[i:]
v, pos = 0, i
while True:
w = self.kids[v].get(s[pos])
if w is None: # fell off at a node: hang a leaf
self.kids[v][s[pos]] = self._new(pos, n, i)
break
a, b = self.start[w], self.end[w]
k = 0
while k < b - a and s[a + k] == s[pos + k]:
k += 1
if k == b - a: # whole edge matched: go down
v, pos = w, pos + k
continue
mid = self._new(a, a + k, -1) # mismatch inside the edge: split it
self.kids[v][s[a]] = mid
self.start[w] = a + k
self.kids[mid][s[a + k]] = w
self.kids[mid][s[pos + k]] = self._new(pos + k, n, i)
break
# Post-order pass: leaves below each node and string depth of each node.
cnt = len(self.start)
self.leaves, self.depth = [0] * cnt, [0] * cnt
order, stack = [], [0]
while stack:
v = stack.pop()
order.append(v)
for w in self.kids[v].values():
self.depth[w] = self.depth[v] + self.end[w] - self.start[w]
stack.append(w)
for v in reversed(order):
self.leaves[v] = 1 if not self.kids[v] else sum(self.leaves[w] for w in self.kids[v].values())
def _new(self, start: int, end: int, suffix: int) -> int:
self.start.append(start)
self.end.append(end)
self.kids.append({})
self.suffix.append(suffix)
return len(self.start) - 1
def _locus(self, p: str) -> int:
"""Node at or just below the end of p's path, or -1 if p is not a substring."""
v, k = 0, 0
while k < len(p):
w = self.kids[v].get(p[k])
if w is None:
return -1
a, b = self.start[w], self.end[w]
j = 0
while j < b - a and k < len(p):
if self.s[a + j] != p[k]:
return -1
j += 1
k += 1
v = w
return v
def contains(self, p: str) -> bool:
return self._locus(p) != -1
def count(self, p: str) -> int:
v = self._locus(p)
return 0 if v == -1 else self.leaves[v]
def distinct_substrings(self) -> int:
n = len(self.s) # an edge ending at n carries the '$': drop 1
return sum(self.end[v] - self.start[v] - (self.end[v] == n) for v in range(1, len(self.start)))
def longest_repeated(self) -> str:
best = max((v for v in range(len(self.start)) if self.kids[v]), key=lambda v: self.depth[v])
# Walk up is not stored, so read the label from any leaf below: it starts with the path.
v = best
while self.kids[v]:
v = next(iter(self.kids[v].values()))
return self.s[self.suffix[v]:self.suffix[v] + self.depth[best]]
def node_count(self) -> int:
return len(self.start)
if __name__ == "__main__":
import random
st = NaiveSuffixTree("banana")
assert st.node_count() == 11 # root + 3 internal + 7 leaves
assert st.contains("nan") and not st.contains("nab")
assert st.count("ana") == 2 and st.count("a") == 3 and st.count("x") == 0
assert st.distinct_substrings() == 15
assert st.longest_repeated() == "ana"
rng = random.Random(1)
for _ in range(2000): # compare with brute force
t = "".join(rng.choice("ab") for _ in range(rng.randint(1, 25)))
st = NaiveSuffixTree(t)
subs = {t[i:j] for i in range(len(t)) for j in range(i + 1, len(t) + 1)}
assert st.distinct_substrings() == len(subs)
assert st.node_count() <= 2 * (len(t) + 1)
p = "".join(rng.choice("ab") for _ in range(rng.randint(1, 4)))
assert st.count(p) == sum(t.startswith(p, i) for i in range(len(t)))
assert len(st.longest_repeated()) == max((len(x) for x in subs if st.count(x) >= 2), default=0)
print("python ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
/** Compressed suffix tree built by inserting suffixes one by one: O(n^2) time, O(n) nodes. */
public class NaiveSuffixTree {
final String s;
// Node v owns the edge s[start(v), end(v)) that leads INTO it. Node 0 is the root.
final List<Integer> start = new ArrayList<>(), end = new ArrayList<>(), suffix = new ArrayList<>();
final List<Map<Character, Integer>> kids = new ArrayList<>();
int[] leaves, depth;
NaiveSuffixTree(String text) {
s = text + "$";
int n = s.length();
newNode(0, 0, -1);
for (int i = 0; i < n; i++) { // insert suffix s[i..]
int v = 0, pos = i;
while (true) {
Integer w = kids.get(v).get(s.charAt(pos));
if (w == null) { // fell off at a node: hang a leaf
kids.get(v).put(s.charAt(pos), newNode(pos, n, i));
break;
}
int a = start.get(w), b = end.get(w), k = 0;
while (k < b - a && s.charAt(a + k) == s.charAt(pos + k)) k++;
if (k == b - a) { v = w; pos += k; continue; } // whole edge matched: go down
int mid = newNode(a, a + k, -1); // mismatch inside the edge: split it
kids.get(v).put(s.charAt(a), mid);
start.set(w, a + k);
kids.get(mid).put(s.charAt(a + k), w);
kids.get(mid).put(s.charAt(pos + k), newNode(pos + k, n, i));
break;
}
}
// Post-order pass: leaves below each node and string depth of each node.
int cnt = start.size();
leaves = new int[cnt];
depth = new int[cnt];
List<Integer> order = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
while (!stack.isEmpty()) {
int v = stack.pop();
order.add(v);
for (int w : kids.get(v).values()) {
depth[w] = depth[v] + end.get(w) - start.get(w);
stack.push(w);
}
}
for (int idx = order.size() - 1; idx >= 0; idx--) {
int v = order.get(idx);
if (kids.get(v).isEmpty()) leaves[v] = 1;
else for (int w : kids.get(v).values()) leaves[v] += leaves[w];
}
}
private int newNode(int st, int en, int suf) {
start.add(st); end.add(en); suffix.add(suf); kids.add(new HashMap<>());
return start.size() - 1;
}
/** Node at or just below the end of p's path, or -1 if p is not a substring. */
private int locus(String p) {
int v = 0, k = 0;
while (k < p.length()) {
Integer w = kids.get(v).get(p.charAt(k));
if (w == null) return -1;
int a = start.get(w), b = end.get(w);
for (int j = 0; j < b - a && k < p.length(); j++, k++) {
if (s.charAt(a + j) != p.charAt(k)) return -1;
}
v = w;
}
return v;
}
boolean contains(String p) { return locus(p) != -1; }
int count(String p) { int v = locus(p); return v == -1 ? 0 : leaves[v]; }
long distinctSubstrings() {
long total = 0;
int n = s.length();
for (int v = 1; v < start.size(); v++) total += end.get(v) - start.get(v) - (end.get(v) == n ? 1 : 0);
return total;
}
String longestRepeated() {
int best = 0;
for (int v = 0; v < start.size(); v++) if (!kids.get(v).isEmpty() && depth[v] > depth[best]) best = v;
int v = best;
while (!kids.get(v).isEmpty()) v = kids.get(v).values().iterator().next();
return s.substring(suffix.get(v), suffix.get(v) + depth[best]);
}
int nodeCount() { return start.size(); }
public static void main(String[] args) {
NaiveSuffixTree st = new NaiveSuffixTree("banana");
check(st.nodeCount() == 11); // root + 3 internal + 7 leaves
check(st.contains("nan") && !st.contains("nab"));
check(st.count("ana") == 2 && st.count("a") == 3 && st.count("x") == 0);
check(st.distinctSubstrings() == 15);
check(st.longestRepeated().equals("ana"));
Random rng = new Random(1);
for (int it = 0; it < 2000; it++) { // compare with brute force
int len = 1 + rng.nextInt(25);
StringBuilder b = new StringBuilder();
for (int i = 0; i < len; i++) b.append(rng.nextBoolean() ? 'a' : 'b');
String t = b.toString();
NaiveSuffixTree tr = new NaiveSuffixTree(t);
Set<String> subs = new HashSet<>();
for (int i = 0; i < len; i++) for (int j = i + 1; j <= len; j++) subs.add(t.substring(i, j));
check(tr.distinctSubstrings() == subs.size());
check(tr.nodeCount() <= 2 * (len + 1));
String p = t.substring(rng.nextInt(len));
if (p.length() > 4) p = p.substring(0, 4);
int occ = 0;
for (int i = 0; i + p.length() <= len; i++) if (t.startsWith(p, i)) occ++;
check(tr.count(p) == occ);
int lr = 0;
for (String x : subs) if (x.length() > lr && t.indexOf(x) != t.lastIndexOf(x)) lr = x.length();
check(tr.longestRepeated().length() == lr);
}
System.out.println("java ok");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError();
}
}
#include <cassert>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;
// Compressed suffix tree built by inserting suffixes one by one: O(n^2) time, O(n) nodes.
struct NaiveSuffixTree {
string s;
// Node v owns the edge s[start[v], end[v]) that leads INTO it. Node 0 is the root.
vector<int> start, end_, suffix, leaves, depth;
vector<map<char, int>> kids;
explicit NaiveSuffixTree(const string& text) : s(text + "$") {
int n = (int)s.size();
newNode(0, 0, -1);
for (int i = 0; i < n; i++) { // insert suffix s[i..]
int v = 0, pos = i;
while (true) {
auto it = kids[v].find(s[pos]);
if (it == kids[v].end()) { // fell off at a node: hang a leaf
int leaf = newNode(pos, n, i);
kids[v][s[pos]] = leaf;
break;
}
int w = it->second, a = start[w], b = end_[w], k = 0;
while (k < b - a && s[a + k] == s[pos + k]) k++;
if (k == b - a) { v = w; pos += k; continue; } // whole edge matched: go down
int mid = newNode(a, a + k, -1); // mismatch inside the edge: split it
kids[v][s[a]] = mid;
start[w] = a + k;
kids[mid][s[a + k]] = w;
int leaf = newNode(pos + k, n, i);
kids[mid][s[pos + k]] = leaf;
break;
}
}
// Post-order pass: leaves below each node and string depth of each node.
int cnt = (int)start.size();
leaves.assign(cnt, 0);
depth.assign(cnt, 0);
vector<int> order, stack = {0};
while (!stack.empty()) {
int v = stack.back();
stack.pop_back();
order.push_back(v);
for (auto& [c, w] : kids[v]) {
depth[w] = depth[v] + end_[w] - start[w];
stack.push_back(w);
}
}
for (int idx = (int)order.size() - 1; idx >= 0; idx--) {
int v = order[idx];
if (kids[v].empty()) leaves[v] = 1;
else for (auto& [c, w] : kids[v]) leaves[v] += leaves[w];
}
}
int newNode(int st, int en, int suf) {
start.push_back(st); end_.push_back(en); suffix.push_back(suf); kids.emplace_back();
return (int)start.size() - 1;
}
// Node at or just below the end of p's path, or -1 if p is not a substring.
int locus(const string& p) const {
int v = 0, k = 0, m = (int)p.size();
while (k < m) {
auto it = kids[v].find(p[k]);
if (it == kids[v].end()) return -1;
int w = it->second;
for (int j = 0; j < end_[w] - start[w] && k < m; j++, k++)
if (s[start[w] + j] != p[k]) return -1;
v = w;
}
return v;
}
bool contains(const string& p) const { return locus(p) != -1; }
int count(const string& p) const { int v = locus(p); return v == -1 ? 0 : leaves[v]; }
long long distinctSubstrings() const {
long long total = 0;
int n = (int)s.size();
for (int v = 1; v < (int)start.size(); v++) total += end_[v] - start[v] - (end_[v] == n ? 1 : 0);
return total;
}
string longestRepeated() const {
int best = 0;
for (int v = 0; v < (int)start.size(); v++)
if (!kids[v].empty() && depth[v] > depth[best]) best = v;
int v = best;
while (!kids[v].empty()) v = kids[v].begin()->second;
return s.substr(suffix[v], depth[best]);
}
int nodeCount() const { return (int)start.size(); }
};
int main() {
NaiveSuffixTree st("banana");
assert(st.nodeCount() == 11); // root + 3 internal + 7 leaves
assert(st.contains("nan") && !st.contains("nab"));
assert(st.count("ana") == 2 && st.count("a") == 3 && st.count("x") == 0);
assert(st.distinctSubstrings() == 15);
assert(st.longestRepeated() == "ana");
mt19937 rng(1);
for (int it = 0; it < 2000; it++) { // compare with brute force
int len = 1 + (int)(rng() % 25);
string t;
for (int i = 0; i < len; i++) t += (rng() & 1) ? 'a' : 'b';
NaiveSuffixTree tr(t);
set<string> subs;
for (int i = 0; i < len; i++) for (int j = i + 1; j <= len; j++) subs.insert(t.substr(i, j - i));
assert(tr.distinctSubstrings() == (long long)subs.size());
assert(tr.nodeCount() <= 2 * (len + 1));
string p = t.substr(rng() % len, 4);
int occ = 0;
for (int i = 0; i + (int)p.size() <= len; i++) if (t.compare(i, p.size(), p) == 0) occ++;
assert(tr.count(p) == occ);
size_t lr = 0;
for (auto& x : subs) if (x.size() > lr && t.find(x) != t.rfind(x)) lr = x.size();
assert(tr.longestRepeated().size() == lr);
}
cout << "c++ ok" << endl;
return 0;
}
/** Compressed suffix tree built by inserting suffixes one by one: O(n^2) time, O(n) nodes. */
class NaiveSuffixTree {
readonly s: string;
// Node v owns the edge s[start[v], end[v]) that leads INTO it. Node 0 is the root.
private start: number[] = [];
private end: number[] = [];
private suffix: number[] = [];
private kids: Map<string, number>[] = [];
private leaves: number[] = [];
private depth: number[] = [];
constructor(text: string) {
const s = (this.s = text + "$");
const n = s.length;
this.newNode(0, 0, -1);
for (let i = 0; i < n; i++) { // insert suffix s[i..]
let v = 0, pos = i;
while (true) {
const w = this.kids[v].get(s[pos]);
if (w === undefined) { // fell off at a node: hang a leaf
this.kids[v].set(s[pos], this.newNode(pos, n, i));
break;
}
const a = this.start[w], b = this.end[w];
let k = 0;
while (k < b - a && s[a + k] === s[pos + k]) k++;
if (k === b - a) { v = w; pos += k; continue; } // whole edge matched: go down
const mid = this.newNode(a, a + k, -1); // mismatch inside the edge: split it
this.kids[v].set(s[a], mid);
this.start[w] = a + k;
this.kids[mid].set(s[a + k], w);
this.kids[mid].set(s[pos + k], this.newNode(pos + k, n, i));
break;
}
}
// Post-order pass: leaves below each node and string depth of each node.
const cnt = this.start.length;
this.leaves = new Array<number>(cnt).fill(0);
this.depth = new Array<number>(cnt).fill(0);
const order: number[] = [], stack: number[] = [0];
while (stack.length > 0) {
const v = stack.pop()!;
order.push(v);
for (const w of this.kids[v].values()) {
this.depth[w] = this.depth[v] + this.end[w] - this.start[w];
stack.push(w);
}
}
for (let idx = order.length - 1; idx >= 0; idx--) {
const v = order[idx];
if (this.kids[v].size === 0) this.leaves[v] = 1;
else for (const w of this.kids[v].values()) this.leaves[v] += this.leaves[w];
}
}
private newNode(st: number, en: number, suf: number): number {
this.start.push(st); this.end.push(en); this.suffix.push(suf); this.kids.push(new Map());
return this.start.length - 1;
}
/** Node at or just below the end of p's path, or -1 if p is not a substring. */
private locus(p: string): number {
let v = 0, k = 0;
while (k < p.length) {
const w = this.kids[v].get(p[k]);
if (w === undefined) return -1;
for (let j = 0; j < this.end[w] - this.start[w] && k < p.length; j++, k++) {
if (this.s[this.start[w] + j] !== p[k]) return -1;
}
v = w;
}
return v;
}
contains(p: string): boolean { return this.locus(p) !== -1; }
count(p: string): number { const v = this.locus(p); return v === -1 ? 0 : this.leaves[v]; }
distinctSubstrings(): number {
const n = this.s.length;
let total = 0;
for (let v = 1; v < this.start.length; v++) total += this.end[v] - this.start[v] - (this.end[v] === n ? 1 : 0);
return total;
}
longestRepeated(): string {
let best = 0;
for (let v = 0; v < this.start.length; v++) {
if (this.kids[v].size > 0 && this.depth[v] > this.depth[best]) best = v;
}
let v = best;
while (this.kids[v].size > 0) v = this.kids[v].values().next().value!;
return this.s.slice(this.suffix[v], this.suffix[v] + this.depth[best]);
}
nodeCount(): number { return this.start.length; }
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(what);
}
const st = new NaiveSuffixTree("banana");
check(st.nodeCount() === 11, "nodes"); // root + 3 internal + 7 leaves
check(st.contains("nan") && !st.contains("nab"), "contains");
check(st.count("ana") === 2 && st.count("a") === 3 && st.count("x") === 0, "count");
check(st.distinctSubstrings() === 15, "distinct");
check(st.longestRepeated() === "ana", "repeated");
let seed = 1;
const rand = (): number => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
for (let it = 0; it < 2000; it++) { // compare with brute force
const len = 1 + Math.floor(rand() * 25);
let t = "";
for (let i = 0; i < len; i++) t += rand() < 0.5 ? "a" : "b";
const tr = new NaiveSuffixTree(t);
const subs = new Set<string>();
for (let i = 0; i < len; i++) for (let j = i + 1; j <= len; j++) subs.add(t.slice(i, j));
check(tr.distinctSubstrings() === subs.size, "random distinct");
check(tr.nodeCount() <= 2 * (len + 1), "random size");
const p = t.slice(Math.floor(rand() * len)).slice(0, 4);
let occ = 0;
for (let i = 0; i + p.length <= len; i++) if (t.startsWith(p, i)) occ++;
check(tr.count(p) === occ, "random count");
let lr = 0;
for (const x of subs) if (x.length > lr && t.indexOf(x) !== t.lastIndexOf(x)) lr = x.length;
check(tr.longestRepeated().length === lr, "random repeated");
}
console.log("ts ok");
Notes on the code:
- Terminator. The builders append
$and assume it does not occur in the input. For arbitrary bytes, use a value outside the alphabet (−1 in an integer array). - Children maps. Hash maps give expected child lookup but cost a lot of memory per node; arrays of size are faster for DNA ( with
$) and wasteful for Unicode. Sorted children (aTreeMap/std::map) give lexicographic DFS order, which is how you read a suffix array off the tree. - No recursion. All traversals use explicit stacks; a recursive DFS on
aaaa…awould recurse deep and overflow the call stack. longest_repeatedfinds the deepest internal node and reads its label from any leaf below it (the leaf's suffix starts with the node's path).
Generalized suffix trees
A generalized suffix tree (GST) holds all suffixes of several strings . Two standard ways to build one:
- Concatenate with distinct terminators, , and build one suffix tree. Leaf edges then run across terminators into the next string; either cut every leaf label at its first terminator, or simply ignore anything after a terminator when reading labels.
- Insert the strings one after another into the same tree with Ukkonen's algorithm, resetting the active point to the root for each new string (Gusfield §6.4).
Each leaf records which string (its "colour") and which position it came from.
Longest common substring of strings
A substring common to all strings is a path whose subtree contains leaves of all colours. So:
- Compute, for every internal node, the number of distinct colours among the leaves below it.
- The answer is the deepest (by string depth) node whose colour count is .
Colour sets as bitmasks merge bottom-up in where is the machine word size; for large , Lucas Hui's method ("Color set size problem with applications to string matching", CPM 1992) counts distinct colours for all nodes in using lowest common ancestors of same-coloured leaves in DFS order. For two strings this is just "deepest node with leaves from both". The suffix-array version is the sliding window over colours from the previous lesson.
The same colour counts answer "longest substring common to at least of the strings" and "for each string, its shortest substring that occurs in no other" (a leaf's parent depth plus one, if the parent's colour count is 1).
Matching statistics
For a text and a reference , the matching statistics are = the length of the longest prefix of that occurs somewhere in . William Chang and Eugene Lawler ("Sublinear approximate string matching and biological applications", Algorithmica 12, 1994) computed all of them in with the suffix tree of :
- Walk down the tree from the root as far as possible; the depth reached is .
- To go from to , drop the first letter: follow the suffix link from the last node above the current locus, then skip/count back down by the remaining length, and continue matching letters of .
It is Ukkonen's active-point movement, used as a reader instead of a builder. Matching statistics give the longest common substring of and (the maximum ) in with the tree of only, and they are the backbone of tools that find maximal exact matches (MEMs) between genomes. The suffix automaton does the same walk even more simply.
Suffix tree vs suffix array vs suffix automaton
| Suffix tree | Suffix array (+ LCP) | Suffix automaton | |
|---|---|---|---|
| What it is | Compressed trie of all suffixes | Sorted suffix starts (+ neighbour LCPs) | Smallest DFA accepting all substrings |
| Size | nodes, edges | integers (+ for LCP) | states, transitions |
| Memory in practice | ~10–20 bytes/char engineered (Kurtz 1999), often far more | 4 bytes/char for SA, ~8–9 with LCP and text | depends on transition storage; typically larger than SA |
| Build | Ukkonen/McCreight; tricky | doubling (simple) or SA-IS | , about 30 lines |
| Online (append a letter) | yes (Ukkonen) | no | yes |
| Pattern query | , or with LCP-LR | ||
| Occurrence positions | leaves below locus | contiguous SA block | needs extra links or end-position sets |
| Lexicographic order, -th substring | DFS with sorted children | natural | possible with DP over paths |
| Longest common substring of 2 | GST, deepest bi-coloured node | SA of A#B, adjacent suffixes | Automaton of A, walk B |
| Cache behaviour | poor (pointer chasing) | good (arrays) | medium |
| Typical contest use | rare | very common | very common |
How they relate: the internal nodes of the suffix tree of are the LCP intervals of its suffix array; and the suffix links of the suffix automaton of form the suffix tree of the reversed string (Blumer et al., 1985). Learn one deeply and the other two are views of the same structure.
When to use which
In contests:
- Default to suffix array + LCP (with a sparse table for arbitrary LCP queries) for "one string, many substring questions", especially anything involving lexicographic order.
- Use a suffix automaton for counting distinct substrings, occurrences, longest common substring of two strings, and anything that needs online appends. It is the shortest code with guarantees.
- Write a suffix tree only if you have a tested Ukkonen in your library and the problem is naturally about branching structure (e.g. colour counting over a GST). Many competitors never write one.
- For , the naive compressed tree (or even a trie of suffixes with nodes) is often enough and much safer.
In production:
- Large, static texts (genomes, corpora, logs): suffix arrays, enhanced suffix arrays, or compressed indexes (FM-index). Memory dominates, and the tree's 10–20 bytes per character (plus pointer chasing) loses to 4 bytes per character or less.
- Small or medium texts with complex, tree-shaped queries (repeat analysis, string-based clustering, some compiler and data-compression tools): suffix trees are fine and the code is clearer.
- Streaming text with interleaved queries: Ukkonen or a suffix automaton.
- If you can, use a library: SeqAn (C++) offers suffix trees, enhanced suffix arrays and FM-indexes behind one interface; SDSL-lite offers compressed suffix trees.
Real-world uses
- Whole-genome alignment: MUMmer. MUMmer 1–3 (Delcher et al. 1999; Kurtz et al., "Versatile and open software for comparing large genomes", Genome Biology 5:R12, 2004) used a suffix tree of the reference to find maximal unique matches between genomes, then chained them into alignments. That is the matching-statistics walk above. MUMmer4 (Marçais et al. 2018) replaced the tree with a suffix array to cut memory, which is the general trend.
- Repeat finding: REPuter. Kurtz and Schleiermacher's REPuter (Bioinformatics 15(5), 1999) finds exact and approximate repeats in genomes from a space-efficient suffix tree, the representation from Kurtz's 1999 space paper.
- Lazy suffix trees. Giegerich, Kurtz and Stoye ("Efficient implementation of lazy suffix trees", Software: Practice and Experience 33(11), 2003) build only the parts of the tree that queries visit, a practical compromise used in sequence-analysis tools.
- Data compression. Suffix trees (and their relatives) were used to implement LZ77-style "longest previous match" searches and the PPM family of context models, which need "longest context seen before" queries; modern compressors mostly use hash chains, binary trees or suffix arrays for this.
- Teaching and theory. Many linear-time string results (longest common substring, all maximal repeats, all tandem repeats, LCE queries) were first proved with suffix trees, as catalogued by Gusfield (1997). Even when the production code uses a suffix array, the proof often reasons about the tree.
Pitfalls & edge cases
- Forgetting the terminator. Without a unique
$, some suffixes end inside edges, leaf counts are wrong, and "every suffix has a leaf" fails. The final Ukkonen phase on$is what makes the implicit tree explicit. - A terminator that occurs in the text. The constructor must reject it (the Python code raises
ValueError). - Setting suffix links at the wrong time. The most common Ukkonen bug: a node created by a split must get its link from the next extension in the same phase (the next split, or the active node when Rule 3 or a node-level Rule 2 happens). Forgetting the Rule 3 case leaves a link pointing to the root and silently breaks later phases on some inputs. Random testing against the naive tree catches this quickly; small hand examples often do not.
- Walk-down with
>instead of>=. If the active length equals the edge length, the active point is exactly at the child node; you must move to it before looking for the next letter. Using>compares the letter past the end of the edge. - Leaf ends that are copied, not shared. If each leaf stores its own end integer, you must update all of them every phase, which is . Share one variable (or use a sentinel meaning "current end").
- Recursion depth. Trees of repetitive strings are levels deep. Use iterative traversals.
- Memory blow-up. A node object with a hash map per node costs hundreds of bytes in Java, Python or JavaScript. For that is hundreds of megabytes. Use arrays (struct-of-arrays) and small fixed alphabets where possible.
- Unicode. Edges index into the string; in Java/TypeScript that means UTF-16 code units, so a surrogate pair can be split across an edge boundary. Index code points or bytes consistently.
Variations
- Implicit suffix trees (no terminator): what Ukkonen maintains between phases; useful when you only need "is it a substring" for a growing text.
- Suffix trees for integer alphabets (Farach 1997): recursion on odd/even suffixes, for alphabets of size polynomial in .
- Compressed suffix trees (Sadakane 2007): a compressed suffix array + compressed LCP + balanced-parentheses tree topology, a few bits per character, with all navigation operations in polylog time. Available in SDSL-lite.
- Sparse suffix trees: index only some suffixes (e.g. word starts).
- Position heaps and suffix trays: alternatives with different query/space trade-offs (mainly theoretical interest).
- Suffix trees of trees and of 2-D arrays: generalizations used in XML indexing and image matching.
- Directed acyclic word graph (DAWG) / suffix automaton: merge isomorphic subtrees of the suffix trie instead of compressing chains; see Suffix Automaton.
Practice ladder
Each problem is described in my own words; follow the link for the full statement. Every one of them can be solved with a suffix tree; the hints also say when a suffix array or automaton is the easier route.
1. Finding Patterns (CSES 2102) — For each of many patterns, does it occur in the string? Teaches walking the tree.
Solution
Build the tree once; each query is contains(p), . With the naive builder this is fine for short strings; for the full limits ( up to ) use Ukkonen, a suffix array, or a suffix automaton.
def finding_patterns(text, patterns):
st = SuffixTree(text) # Ukkonen
return ["YES" if st.contains(p) else "NO" for p in patterns]
2. Counting Patterns (CSES 2103) — Count occurrences of each pattern. Teaches "leaves below the locus".
Solution
Precompute leaf counts in one post-order pass, then count(p) is the leaf count of the node at or below the end of 's path (the count method in the four-language code). banana, ana → 2; a → 3.
3. Pattern Positions (CSES 2104) — First position of each pattern. Teaches storing one aggregate per node.
Hint
In the post-order pass, store the minimum leaf index below every node. The answer for is that minimum at its locus, plus 1.
4. Distinct Substrings (CSES 2105) — Count distinct substrings. Teaches "sum of edge lengths".
Solution
Every point on every edge (excluding the terminator) is one distinct substring, so the count is the total length of all edge labels minus one for each leaf edge (its $). distinct_substrings() in both implementations; banana → 15.
5. Repeating Substring (CSES 2106) — Longest substring occurring at least twice. Teaches "deepest internal node".
Hint
longest_repeated(). A substring occurring twice is a path whose locus has at least two leaves below, so it is a prefix of an internal node's path; the deepest internal node is the longest such path.
6. Longest Duplicate Substring (LeetCode 1044) — Same as 5 with . Teaches that a naive tree is too slow in the worst case.
Hint
Naive construction is on aaaa…, about steps: too slow in Python. Use Ukkonen or the suffix-array answer ( LCP).
7. Longest Common Substring (SPOJ LCS) — Longest common substring of two strings of length up to 250,000. Teaches the generalized tree or matching statistics.
Hint
Build the tree of A#B$; the answer is the deepest internal node with leaves from both strings (a leaf is from A if its suffix starts before #). Or build the tree of A only and compute matching statistics of B. Many people solve it with a suffix automaton of A, which is the same walk.
8. Longest Common Substring II (SPOJ LCS2) — Same for up to 10 strings. Teaches colour counting in a GST.
Hint
Distinct separators; for each node, the bitmask of colours below it (10 bits); answer = deepest node with mask (1 << k) - 1.
9. Longest Common Subpath (LeetCode 1923) — Longest common contiguous sub-array of many integer arrays. Teaches GST over integer alphabets.
Hint
Common solutions use binary search + rolling hash. The deterministic route is a generalized suffix structure over integers (suffix array of all paths joined with unique separators, then a sliding window covering all colours). The total length is up to .
10. String (Codeforces 128B) — The -th lexicographically smallest substring, counting repeated occurrences separately. Teaches DFS in sorted order with occurrence counts.
Hint
DFS with sorted children; at each node, the strings ending on its edge each occur (leaves below) times. Subtract whole subtrees from until it fits. Constraints allow ; the suffix automaton solution is the common one.
11. Little Elephant and Strings (Codeforces 204E) — For each string, count its substrings that occur in at least of the given strings. Teaches GST + colour counts + per-leaf summation.
Hint
Build a GST, compute distinct-colour counts per node (Hui's method or small-to-large merging of sets). For each suffix (leaf), the substrings starting there that qualify are the prefixes up to the depth of the deepest ancestor with colour count ; sum those depths per string.
12. Good Substrings (Codeforces 316G3) — Count distinct substrings of whose occurrence counts in several rule strings lie within given ranges. Teaches a GST with per-colour occurrence counts on each node.
Hint
GST of and all rule strings; for each node, count leaves of each colour below it. Every edge point on a path contributes if the counts at its lower node satisfy all rules and the -count is positive; add qualifying edge lengths.
Common mistakes & interview follow-ups
"What is a suffix tree?" The compressed trie of all suffixes of : leaves, at most internal nodes, edges labelled by index pairs, space.
"Why is it size if there are substrings?" Leaves = suffixes; every internal node branches, so internal < leaves; labels are pointers, not copies.
"Explain Ukkonen in two minutes." Build online. Leaves never stop being leaves, so one global END extends them all for free. If a pending suffix is already present (Rule 3), all shorter ones are too, so stop the phase. Track the longest pending suffix as an active point; after inserting it, jump to the next shorter one via a suffix link in ; skip whole edges by length. Each of these is amortised , so total.
"Why not just use a suffix array?" Usually you should: 3–5× less memory and simpler. Choose the tree for online construction, queries without binary search, or when tree-shaped reasoning (colours, subtrees) makes the solution clear.
"How do you find the longest common substring of 100 strings?" Generalized suffix tree with distinct terminators, colour counts per node (Hui), deepest full-colour node. Or a suffix array with a sliding window.
Mistakes interviewers watch for: no terminator; claiming the tree uses bytes with a small constant; storing edge labels as copied strings ( space); recursive DFS on deep trees; not knowing that suffix arrays and automata usually replace it in practice.
Quick quiz
1. How many leaves and at most how many internal nodes does the suffix tree of a string of length 9 (plus $) have?
Answer
10 leaves, at most 9 internal nodes including the root, so at most 19 nodes.
2. Why does abab need a terminator, concretely?
Answer
ab is a prefix of abab and b a prefix of bab, so their paths end inside edges, not at leaves. Only 2 leaves would exist for 4 suffixes.
3. In phase 4 of the abcabxabcd$ run, the remainder is 2. Which suffixes are pending?
Answer
ab and b. Both are already in the tree implicitly (inside the edges abcab and bcab), which is why Rule 3 stopped the phase.
4. What does a suffix link from node abc point to, and why does it exist?
Answer
To node bc. abc is followed by both a and d in the text (it branches), so bc is followed by a and d too, and it must also be a branching node (Lemma 1).
5. In Ukkonen's running-time proof, why can there be at most skip/count jumps in total?
Answer
Each jump decreases the active length by at least 1, and the active length increases only in Rule 3, by 1, at most once per phase.
Further reading / sources
- Esko Ukkonen, "On-line construction of suffix trees", Algorithmica 14(3), 1995, pp. 249–260.
- Peter Weiner, "Linear pattern matching algorithms", 14th Annual IEEE Symposium on Switching and Automata Theory, 1973.
- Edward M. McCreight, "A space-economical suffix tree construction algorithm", Journal of the ACM 23(2), 1976.
- Martin Farach, "Optimal suffix tree construction with large alphabets", FOCS 1997.
- Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997: ch. 5–6 (Ukkonen with the three rules, suffix links, skip/count; generalized suffix trees), ch. 7 (applications, matching statistics).
- Stefan Kurtz, "Reducing the space requirement of suffix trees", Software: Practice and Experience 29(13), 1999, pp. 1149–1171 (PDF).
- Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, "Replacing suffix trees with enhanced suffix arrays", Journal of Discrete Algorithms 2(1), 2004.
- Lucas C. K. Hui, "Color set size problem with applications to string matching", CPM 1992.
- William I. Chang, Eugene L. Lawler, "Sublinear approximate string matching and biological applications", Algorithmica 12, 1994.
- Anselm Blumer et al., "The smallest automaton recognizing the subwords of a text", Theoretical Computer Science 40, 1985.
- Stefan Kurtz et al., "Versatile and open software for comparing large genomes", Genome Biology 5:R12, 2004 (MUMmer 3).
- The classic intuitive walkthrough of the
abcabxabcdexample is a widely cited Stack Overflow answer, "Ukkonen's suffix tree algorithm in plain English"; the table on this page was regenerated by running the code shown, not copied. - The measured numbers (trie vs tree node counts, build timings in Python on an Apple M5, the
banana$andabcabxabcd$trees) were produced by running the code on this page.
Previous lesson: Suffix Automaton · Next lesson: Palindromes & Manacher's Algorithm
Related: Suffix Arrays & LCP · Tries · Aho–Corasick · String Algorithms overview · Course home