From Suffix Trie to Suffix Array: Implicit Nodes and Intervals

Indexing a text for substring search is the problem of storing every suffix in a structure that supports “which suffixes start with this pattern”. The trie answer is immediate: insert all n suffixes into a trie, then a pattern search is a path walk and the matching suffixes are the leaves below the end of the path. The structure is correct and unusable. Its node count is quadratic, and the reason is structural rather than incidental — a trie over suffixes stores, at every node on the path to a suffix, a prefix that recurs at many other positions in the text.

Why the suffix trie is quadratic

Take a text of n characters with no repeated structure to speak of, and insert its n suffixes. The suffix starting at position i has length n − i, so the total number of characters across all suffixes is n(n+1)/2. A trie has at most one node per distinct prefix of an inserted string, and the prefixes of suffixes are exactly the substrings of the text. So the node count is bounded by the number of distinct substrings, which for a random text is Θ(n²). For a text of one million characters that bound is on the order of 10¹² nodes, which is not a structure that can exist.

Sharing among the suffixes does occur — suffixes that begin with the same character share the first edge, and the trie’s top levels are dense — but the sharing only reduces the count by a constant factor for a random text. The quadratic term dominates, and no node representation fixes it, because the nodes are the information.

Removing the unary chains

The first compression is the one already applied to ordinary tries: a node with one child carries no branching information. Compress those away and what remains is a node per branching position plus a leaf per suffix. Since a tree with L leaves has at most L − 1 internal nodes of degree two or more, the node count becomes O(n): at most 2n nodes for n suffixes.

That is the suffix tree, and its node count is linear. The edges carry labels — substrings of the text — and the standard implementation stores each label as a pair (start offset, length) rather than as a copied string, so an edge costs two integers and no text bytes. A traversal that needs the actual characters reads them from the original text at the stored offset, which is why the text must remain in memory alongside the tree.

The linear node count comes with a new problem. Positions that are not branching points no longer have nodes, so a pattern that ends in the middle of an edge ends at an implicit node — a position inside an edge label. Operations that would attach to that position, such as inserting a new suffix during construction, must split the edge, creating an explicit node where there was an implicit one. McCreight’s construction and Ukkonen’s later online variant are both organized around doing that splitting in linear total time, and the difficulty of those algorithms is entirely about managing implicit nodes without materializing them.

For a static index, though, the tree’s branching structure is not the thing a search needs. A search needs, for each node, the range of suffixes that pass through it. That observation leads to the array.

The leaves in lexicographic order

Sort the n suffixes lexicographically and store their starting offsets in an array of n integers. That is a suffix array. Its size is 4n bytes for 32-bit offsets, or 8n for 64-bit — linear, with a small constant, and with no pointers at all.

The correspondence to the trie is exact and worth stating carefully. A depth-first traversal of a trie emits leaves in lexicographic order, as established in lexicographic enumeration over a trie. So the suffix array is the suffix trie’s leaves, read off in traversal order, with the internal nodes discarded. Every internal node of the trie corresponds to a contiguous interval of the array: the set of suffixes that share a given prefix. The node’s identity survives as a pair of array indices, and its depth survives as the length of the common prefix.

What is lost is the ability to walk down from a node to a specific child, because children were never stored. What replaces it is a binary search over the array: to find the interval for a pattern P, compare P against the suffix at the midpoint, and narrow. Each comparison examines at most |P| characters, so a naive search costs O(|P| log n) character comparisons — worse than the trie’s O(|P|), and with a log factor over a very large n.

The LCP array and what it restores

The log factor is removable, and the mechanism is an array that records, for each adjacent pair in the suffix array, the length of their longest common prefix. The LCP array has n − 1 entries and is itself constructible from the suffix array and the text in linear time.

With it, a search does not compare the pattern against each probed suffix from the beginning. During a binary search the algorithm tracks the pattern’s common prefix with the current low and high bounds; a probe in between shares at least the smaller of those two common-prefix lengths with the pattern, so the comparison can skip that many characters. The total number of character comparisons across the whole search becomes O(|P| + log n), because each comparison either extends the known common prefix — and the extension is bounded by |P| in total — or fails immediately.

/// First index in `sa` whose suffix is not less than `pat`.
fn lower_bound(sa: &[u32], text: &[u8], pat: &[u8]) -> usize {
    let (mut lo, mut hi) = (0usize, sa.len());
    while lo < hi {
        let mid = (lo + hi) / 2;
        let suffix = &text[sa[mid] as usize..];
        if suffix < pat {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

/// Half-open range of suffixes starting with `pat`.
fn search(sa: &[u32], text: &[u8], pat: &[u8]) -> Option<(usize, usize)> {
    let start = lower_bound(sa, text, pat);
    let mut end = start;
    // Suffixes sharing a prefix are adjacent, so the range is found by scanning on.
    while end < sa.len() && text[sa[end] as usize..].starts_with(pat) {
        end += 1;
    }
    (end > start).then_some((start, end))
}

Slice comparison is lexicographic and stops at the first differing byte, so a lower bound costs at most one byte comparison beyond the shared prefix, and the scan outward costs one comparison per reported match. What the code does not exploit is that consecutive probes share a prefix with each other: the search may re-examine bytes that a previous probe already established. The LCP array removes exactly that repetition. Each probe’s comparison can begin at the length of the longest common prefix already known for the interval it sits between, so the total character work over a whole search becomes O(|P| + log n) rather than O(|P| log n).

The trade, stated as a table of constants

Each step in this progression removes a factor of n and adds bookkeeping.

Structure	Space	Pattern search	Construction
Suffix trie	Θ(n²) nodes	O(m)	O(n²)
Suffix tree	O(n) nodes, ~4n pointers	O(m)	O(n)
Suffix array	4n bytes	O(m + log n) with LCP	O(n) suffix sorting

The suffix tree’s O(n) node count is honest but its constant is large: each node holds several integers and several pointers, so a practical suffix tree occupies an order of magnitude more memory than the text it indexes, and a text index that would fit comfortably in memory as an array can fail to fit as a tree. The suffix array occupies four bytes per character — 400 MB for a hundred-million-character text — and the LCP array adds the same again unless it is compressed. The array is why suffix structures became practical on ordinary machines.

The cost is that the array supports a narrower set of operations. Enumerating all substrings with a given frequency, locating the deepest repeat, or walking to a child of a node all require extra machinery: a tree-shaped index over the array’s intervals, or a compressed representation of the LCP values. The suffix array answers “find the occurrences of a pattern” in near-optimal time and answers almost everything else only after reconstruction.

Where the interval view breaks

Two properties of the interval correspondence are easy to misstate.

The interval for a prefix is contiguous, but the range for a substring need not be the interval of a node — it is the interval of an implicit node, which is the sub-range of some explicit node’s interval. Searching for a pattern that ends mid-edge yields a range that is a subset of a node’s range, and the LCP-based search returns it correctly because the search never needed the node. An implementation that tries to identify nodes by their intervals and then assumes every range corresponds to an explicit node will mis-handle exactly the patterns that end inside an edge label.

The second is that the array is over suffixes, not over all substrings. Enumerating distinct substrings, or counting them, requires subtracting LCP values from the suffix lengths; the count of distinct substrings of a text of length n is n(n+1)/2 minus the sum of the LCP array, which is a formula that exists precisely because the trie’s node count is the number of distinct substrings.

The suffix array is the compressed form of a trie whose keys are suffixes, and the compression it achieves is the limit of what prefix sharing can do when the key set is every suffix of one string. Further compression is available by exploiting a different kind of redundancy — repeated structure rather than repeated prefixes — which is the subject of deduplicating trie subtrees.