Ukkonen's Suffix Tree Construction

Implicit Trees and Open Edge Ends

A suffix tree is a compact trie of all suffixes. Edges store intervals into the original text rather than copied substrings: a closed interval $[l,r]$ labels $S[l\dots r]$ and has length $r-l+1$.

Ukkonen processes one symbol per phase. After phase $i$, the implicit tree represents every suffix of $S[0\dots i]$, though some suffixes may end inside edges. Every existing leaf must extend through the new symbol, so all leaves share one mutable end object. Advancing it once extends every leaf in constant time; internal edges retain fixed ends after splitting.

Appending a unique sentinel outside the alphabet forces every suffix to end at a distinct leaf, producing an explicit tree with $O(n)$ nodes and edges.

The Active Point and Remainder

The active point carries (active_node, active_edge, active_length). If the length is zero, it is an explicit node; otherwise the edge selected by the symbol at active_edge contains the point active_length symbols below that node.

remainder counts unresolved suffix extensions in the phase. It increases when a symbol arrives and decreases after leaf creation or splitting. A show-stopper can end a phase with positive remainder because those suffixes are already present implicitly.

Skip/count walks down an entire edge whenever active_length reaches its length. After an extension, root handling shortens the active string from the left; otherwise construction follows a suffix link.

At every extension, the active point denotes the longest suffix of the processed text still requiring work, and remainder counts all unresolved suffix extensions. The active point must be canonical: either active_length = 0, or it lies strictly inside its selected edge after every possible whole-edge walk-down.

Extension Rules and Suffix Links

If an explicit active node has no edge for the new symbol, create an open-ended leaf. If the active point lies inside an edge and its next symbol differs, split the edge, attach its old continuation, and add a new leaf. If the next edge symbol already equals the new symbol, increment active_length and stop the phase: the suffix is already represented.

A suffix link connects an internal node representing $x\alpha$ to the node representing $\alpha$. Internal nodes created during one phase are linked as later extensions reveal their proper suffix contexts, preventing rescans from the root.

Ukkonen extension rules

flowchart TD
    START["Pending suffix; append c"]
    WALK{"Active length spans edge?"}
    DOWN["Walk down edge"]
    EDGE{"Outgoing c edge exists?"}
    LEAF["Create open-ended leaf"]
    NEXT{"Next edge symbol equals c?"}
    STOP["Show-stopper: extend active length"]
    SPLIT["Split edge and add leaf"]
    LINK["Update pending suffix link"]
    RESOLVE["Decrease remainder"]
    MOVE{"Active node is root?"}
    ROOTMOVE["Shorten active string"]
    SUFFIX["Follow suffix link"]
    START --> WALK
    WALK -->|yes| DOWN
    DOWN --> START
    WALK -->|no| EDGE
    EDGE -->|no| LEAF
    EDGE -->|yes| NEXT
    NEXT -->|yes| STOP
    NEXT -->|no| SPLIT
    LEAF --> LINK
    SPLIT --> LINK
    LINK --> RESOLVE
    RESOLVE --> MOVE
    MOVE -->|yes| ROOTMOVE
    MOVE -->|no| SUFFIX

Implementation and Verification

Nodes are addressed by integer ID. The destination node owns the interval labeling its incoming edge. Internal ends are fixed integers; leaves reference the shared mutable End. A unique sentinel is selected before construction.

A leaf's suffix start is $N$ minus its root-to-leaf path length. Verification collects every leaf start, checks the complete permutation $0,\dots,N-1$ for terminated text, and compares suffix order with a naive oracle. Suffix links, skip/count, and the shared leaf end yield $O(n)$ construction for constant-time transitions over a fixed alphabet; ordered maps commonly give $O(n\log\sigma)$.

from dataclasses import dataclass, field
from random import Random


@dataclass
class End:
    value: int


@dataclass
class Node:
    start: int
    end: int | End
    suffix_link: int = 0
    children: dict[str, int] = field(default_factory=dict)


class SuffixTree:
    def __init__(self, text: str) -> None:
        self.original_text = text
        self.sentinel = self._choose_sentinel(text)
        self.text = text + self.sentinel
        self.leaf_end = End(-1)
        self.nodes = [Node(-1, -1, suffix_link=0)]
        self.active_node = 0
        self.active_edge = -1
        self.active_length = 0
        self.remainder = 0

        for position in range(len(self.text)):
            self._extend(position)

    @staticmethod
    def _choose_sentinel(text: str) -> str:
        used = set(text)
        for code_point in range(0x110000):
            candidate = chr(code_point)
            if candidate not in used:
                return candidate
        raise ValueError("text contains every Unicode code point")

    def _edge_end(self, node_id: int) -> int:
        end = self.nodes[node_id].end
        return end.value if isinstance(end, End) else end

    def _edge_length(self, node_id: int) -> int:
        node = self.nodes[node_id]
        return self._edge_end(node_id) - node.start + 1

    def _new_node(self, start: int, end: int | End, suffix_link: int = 0) -> int:
        node_id = len(self.nodes)
        self.nodes.append(Node(start, end, suffix_link))
        return node_id

    def _walk_down(self, node_id: int) -> bool:
        length = self._edge_length(node_id)
        if self.active_length < length:
            return False
        self.active_edge += length
        self.active_length -= length
        self.active_node = node_id
        return True

    def _extend(self, position: int) -> None:
        self.leaf_end.value = position
        self.remainder += 1
        last_internal: int | None = None

        while self.remainder > 0:
            if self.active_length == 0:
                self.active_edge = position

            edge_symbol = self.text[self.active_edge]
            next_node = self.nodes[self.active_node].children.get(edge_symbol)

            if next_node is None:
                leaf = self._new_node(position, self.leaf_end)
                self.nodes[self.active_node].children[edge_symbol] = leaf
                if last_internal is not None:
                    self.nodes[last_internal].suffix_link = self.active_node
                    last_internal = None
            else:
                if self._walk_down(next_node):
                    continue

                next_index = self.nodes[next_node].start + self.active_length
                if self.text[next_index] == self.text[position]:
                    if last_internal is not None and self.active_node != 0:
                        self.nodes[last_internal].suffix_link = self.active_node
                        last_internal = None
                    self.active_length += 1
                    break

                split_end = self.nodes[next_node].start + self.active_length - 1
                split = self._new_node(self.nodes[next_node].start, split_end)
                self.nodes[self.active_node].children[edge_symbol] = split

                leaf = self._new_node(position, self.leaf_end)
                self.nodes[split].children[self.text[position]] = leaf

                self.nodes[next_node].start += self.active_length
                continued = self.text[self.nodes[next_node].start]
                self.nodes[split].children[continued] = next_node

                if last_internal is not None:
                    self.nodes[last_internal].suffix_link = split
                last_internal = split

            self.remainder -= 1

            if self.active_node == 0:
                if self.active_length > 0:
                    self.active_length -= 1
                    self.active_edge = position - self.remainder + 1
            else:
                self.active_node = self.nodes[self.active_node].suffix_link

    def suffix_starts(self) -> list[int]:
        total_length = len(self.text)
        result: list[int] = []
        stack: list[tuple[int, int]] = [(0, 0)]
        while stack:
            node_id, path_length = stack.pop()
            node = self.nodes[node_id]
            if node_id:
                path_length += self._edge_length(node_id)
            if not node.children:
                result.append(total_length - path_length)
            else:
                for child in node.children.values():
                    stack.append((child, path_length))
        return result

    def suffix_array(self) -> list[int]:
        starts = sorted(self.suffix_starts(), key=lambda i: self.text[i:])
        return [i for i in starts if i < len(self.original_text)]

    def edge_labels(self) -> list[str]:
        return [
            self.text[node.start:self._edge_end(node_id) + 1]
            for node_id, node in enumerate(self.nodes)
            if node_id
        ]


def naive_suffix_array(text: str) -> list[int]:
    return sorted(range(len(text)), key=lambda start: text[start:])


if __name__ == "__main__":
    for sample in ["", "a", "aaaaa", "banana", "mississippi", "abcabxabcd", "😀a😀é"]:
        tree = SuffixTree(sample)
        assert sorted(tree.suffix_starts()) == list(range(len(tree.text)))
        assert tree.suffix_array() == naive_suffix_array(sample)
        assert all(tree.edge_labels())
        print(sample, len(tree.nodes), tree.suffix_array())

    rng = Random(20260916)
    for _ in range(300):
        sample = "".join(rng.choice("abc") for _ in range(rng.randrange(20)))
        tree = SuffixTree(sample)
        assert sorted(tree.suffix_starts()) == list(range(len(tree.text)))
        assert tree.suffix_array() == naive_suffix_array(sample)

Cookie Consent

Ukkonen's Suffix Tree Construction

Table of Contents

Implicit Trees and Open Edge Ends

The Active Point and Remainder

Extension Rules and Suffix Links

Implementation and Verification