Ukkonen's Algorithm

Ukkonen's algorithm is an on-line, left-to-right string indexing algorithm in computation and algorithms published by Finnish computer scientist Esko Ukkonen in 1995 that constructs the suffix tree (compacted suffix trie) of a string S of length N in optimal O(N) time (for constant-size alphabets Σ, or O(N log |Σ|) for general ordered alphabets). Prior to Ukkonen's work, linear-time suffix tree construction required either Weiner's algorithm (1973, which scans S right-to-left with large space overhead) or McCreight's algorithm (1976, which requires the entire string in advance to insert suffixes longest-to-shortest).

By processing characters incrementally from left to right (i = 1, 2, …, N) to maintain the implicit suffix tree I_i of each prefix S[1..i], Ukkonen's algorithm operates in an on-line streaming fashion. It reduces the naive O(N³) prefix-extension process to O(N) worst-case time through four coupled innovations: edge-label index compression, a global open-leaf end pointer (the "once a leaf, always a leaf" theorem), early phase termination upon encountering Rule 3 (the showstopper rule), and suffix-link traversal combined with skip/count pointer jumping of the active point.

Explicit Suffix Trees vs. Implicit Suffix Trees

Let S = s₁s₂…s_N be a string of length N over an alphabet Σ.

• The explicit suffix tree T(S) (typically built after appending a unique terminal sentinel character ♯ ∉ Σ at position N) is a rooted directed tree with N leaves in which every internal node (other than possibly the root) has at least two children, every edge is labeled with a nonempty substring of S, no two edges leaving the same node begin with the same character, and the concatenated edge labels along the root-to-leaf paths spell out the N suffixes S[1..N], S[2..N], …, S[N..N] in one-to-one correspondence.
• An implicit suffix tree I_i for the prefix S[1..i] is obtained from the explicit suffix tree of S[1..i]♯ by deleting the terminal symbol ♯ from all edge labels and suppressing any resulting empty-labeled leaf edges and unary (degree-1) internal nodes.

In an implicit suffix tree I_i, every suffix S[j..i] (for 1 ≤ j ≤ i) is spelled out by a unique downward path starting at the root, although if S[j..i] is a proper prefix of an earlier suffix S[k..i] (k < j), its path ends implicitly inside an edge or at an internal node rather than at a dedicated leaf. Appending a unique sentinel ♯ at the final phase i = N forces every previously implicit suffix to branch out into an explicit leaf, converting I_N into the true suffix tree T(S).

The Three Suffix Extension Rules

In phase i + 1 (having already constructed I_i for S[1..i] and now reading character c = S[i + 1]), the conceptual high-level algorithm executes i + 1 extensions j = 1, 2, …, i + 1 to ensure every suffix S[j..i + 1] = S[j..i] · c is present in I_i+1. Locating the end of the path for S[j..i] in the current tree triggers one of three mutually exclusive extension rules:

1. Rule 1 (Leaf Edge Extension): The path for S[j..i] ends at an existing leaf of the tree. Append the new character c = S[i + 1] to the end of the edge label entering that leaf.
2. Rule 2 (New Leaf Branch Creation): The path for S[j..i] ends at a non-leaf location (either inside the middle of an edge or at an internal node) and no outgoing path from that location begins with character c = S[i + 1].
   • If the location is inside the middle of an edge (u, v), first split the edge at that point by inserting a new internal node w.
   • Create a new leaf edge labeled with c = S[i + 1] hanging off that node, representing suffix j.
3. Rule 3 (Implicit Prefix Continuation — Showstopper): The path for S[j..i] ends at a non-leaf location and a path continuing with character c = S[i + 1] already exists in the tree. Do nothing (S[j..i + 1] is already present implicitly in the tree).

1. Edge-Label Index Pairs and the Open-Leaf Global End Pointer

Storing explicit substring copies on tree edges would require O(N²) space. Instead, every edge e stores a pair of integer indices [l, r] into S (representing substring S[l..r] in O(1) space).

Furthermore, observe the Leaf Persistence Lemma ("Once a leaf, always a leaf"): whenever extension j creates a leaf (via Rule 2), that leaf remains a leaf in all subsequent phases i′ > i, so in every subsequent phase it undergoes Rule 1 (extending its right endpoint from i to i + 1). If every leaf edge is stored as an open interval [l, e_global] where e_global is a pointer to a single global integer variable holding the current phase index i, then simply incrementing e_global ← i + 1 at the beginning of phase i + 1 executes all Rule 1 extensions for all existing leaves simultaneously in O(1) time!

2. Monotonicity of Suffix Extensions and the Showstopper Rule

Suppose that in phase i − 1, the last extension that created a leaf (via Rule 1 or Rule 2) was j* − 1, so leaves 1, 2, …, j* − 1 are already handled automatically by incrementing e_global. Phase i therefore resumes at explicit extension j = j*.

What happens as soon as some extension j ≥ j* hits Rule 3 (meaning S[j..i] · c is already present in the tree)? Because S[j + 1..i] is a suffix of S[j..i], the string S[j + 1..i] · c is also already present in the tree! Consequently, all remaining extensions j + 1, …, i + 1 in phase i will also hit Rule 3. Therefore, the moment Rule 3 is encountered, the algorithm halts the current phase and advances to phase i + 1 (setting j* to the extension j where Rule 3 stopped it).

Because each Rule 2 extension increments j* by 1 (and creates one permanent leaf out of at most N total leaves), the total number of Rule 2 executions across all N phases combined is at most N, and the total number of Rule 3 executions across all N phases is at most N (at most one per phase)!

3. Suffix Links, Active Point, and Skip/Count Traversal

To move in O(1) amortized time from the location of S[j..i] (after applying Rule 2) to the location of the next shorter suffix S[j + 1..i], Ukkonen's algorithm maintains:

• Suffix Links: Every internal node v spelling out string xα (where x ∈ Σ is a single character and α ∈ Σ*) stores a suffix link link(v) = u pointing to the internal node u that spells out α (with link(root) = root). Whenever a new internal node w is created by splitting an edge during extension j, extension j + 1 will either find or create the internal node for its suffix α, allowing link(w) to be wired in O(1) time on the very next extension.
• The Active Point: A three-tuple (activeNode, activeEdge, activeLength) specifying where the current implicit suffix S[j*, i] resides in the tree (activeLength characters down the outgoing edge from activeNode starting with character activeEdge).
• Skip/Count Trick: When jumping from activeNode to link(activeNode), if activeLength exceeds the length L = r − l + 1 of the target edge, the algorithm jumps across the entire edge in O(1) time (decrementing activeLength ← activeLength − L and advancing activeNode to the child) rather than comparing character-by-character.

Amortized Potential Analysis of Active-Point Depth

Within computational complexity theory, why do all skip/count downward steps take O(N) total time across the entire algorithm?

• Let d be the node-depth of activeNode. Following a suffix link activeNode ← link(activeNode) decreases the node-depth d by at most 1.
• Each skip/count downward jump increases d by 1 while decreasing activeLength by at least 1.
• In each phase, activeLength increases by at most 1 (when reading S[i + 1], adding N total increments across the run).
• Therefore, the total number of skip/count downward steps across all N phases is bounded by 2N, proving optimal O(N) worst-case time and O(N) space.

Comparison of Full-Text Suffix Indexing Algorithms

1. Whole-Genome Alignment and Exact Seed Finding (MUMmer): Computational genomics tools such as MUMmer construct generalized suffix trees via Ukkonen's algorithm to locate all Maximal Unique Matches (MUMs) and maximal exact repeats between chromosome-scale assemblies in linear O(N + M) time.
2. Longest Common Substring, Palindromes, and Lempel–Ziv (LZ77) Compression: Because Ukkonen's algorithm operates on-line from left to right, sliding-window LZ77 data compressors (gzip, Zstandard) maintain an on-line suffix tree of the recent lookback window to find longest previous factors in O(1) amortized time per byte.
3. Bioinformatic Motif Discovery and Lowest Common Ancestor Queries: Pairing a suffix tree built by Ukkonen's algorithm with constant-time LCA preprocessing (or Tarjan's off-line lowest common ancestors algorithm) answers Longest Common Extension (LCE) queries between any two genomic coordinates in O(1) time, accelerating k-mismatch alignment via dynamic programming and suffix array construction.

How does Ukkonen's algorithm convert the final implicit suffix tree into a true explicit suffix tree?

At the end of the string S[1..N], appending a unique terminal character ♯ that never appeared in S[1..N] forces every remaining implicit suffix (from the current j* up to N + 1) to fail Rule 3 and execute Rule 2, branching out into its own explicit leaf in O(N) final steps.

Why is an active point needed instead of jumping directly between suffix leaves?

Suffix links are defined on internal nodes, not inside the middle of compressed multi-character edges. Because the implicit suffixes S[j*, i] waiting for Rule 3 to break can end in the middle of an edge, the activePoint tracks the nearest ancestor internal node (activeNode) plus the character offset (activeLength) down the outgoing edge (activeEdge).

1. Ukkonen, E. (1995). "On-line construction of suffix trees." Algorithmica, 14(3), 249–260. https://doi.org/10.1007/BF01206331
2. Weiner, P. (1973). "Linear pattern matching algorithms." Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT/FOCS), 1–11. https://doi.org/10.1109/SWAT.1973.13
3. McCreight, E. M. (1976). "A space-economical suffix tree construction algorithm." Journal of the ACM, 23(2), 262–272. https://doi.org/10.1145/321941.321946
4. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. https://doi.org/10.1017/CBO9780511574931