Suffix Trees & Ukkonen's Online O(N) Construction: Active Point & Suffix Links

1. Structural Anatomy of a Compressed Suffix Tree

Given $S[0..N-1]$ terminated by a unique sentinel $S[N-1] = \texttt{'\$'}$ ($\texttt{'\$'} \notin \Sigma$), the Suffix Tree $\mathcal{T}(S)$ is the compressed Radix Tree of all $N$ non-empty suffixes $S[0..N-1], S[1..N-1], \dots, S[N-1..N-1]$:

• Bounded Vertex Count: Because $\texttt{'\$'}$ is unique to the end of $S$, no non-empty suffix is a prefix of any other suffix. Thus all $N$ suffixes end at $N$ distinct leaves. Every internal node (except possibly the root if $N=1$) has branching degree $\ge 2$, which implies $\le N - 1$ internal nodes and $\le 2N - 1$ total vertices.
• $O(1)$-Space Edge Slices: Instead of copying substring characters onto edges, each edge $u \to v$ stores two integers $(l, r)$ representing the half-open or closed substring $S[l..r]$. Thus the entire tree takes $O(N)$ words of memory.
• Universal Substring Property: Every substring of $S$ is a prefix of some suffix of $S$. Therefore, a pattern $P[0..M-1]$ occurs in $S$ if and only if $P$ can be spelled out from the root of $\mathcal{T}(S)$ in $O(M)$ time; the leaves in the subtree below the locus of $P$ give all occurrence start positions!

2. Ukkonen's Three Extension Rules & Amortized Linearity

In Phase $i$ ($i = 0..N-1$), Ukkonen's algorithm implicitly maintains the count $\text{rem}$ (remainder) of suffixes waiting to be explicitly branched, alongside the Active Point $(\text{active\_node}, \text{active\_edge}, \text{active\_len})$ identifying the locus of the longest suffix of $S[0..i-1]$ that already appeared earlier in $S$ (so it sits inside the tree rather than at a leaf):

1. Rule 1 (Leaf Extension — Free): Any suffix $S[j..i-1]$ that already ended at a leaf simply appends $S[i]$. By storing leaf right endpoints as $\infty$ (implicitly the current phase index $i$), all existing leaves extend simultaneously in $O(1)$ time!
2. Rule 2 (Branch Creation — New Leaf): While $\text{rem} > 0$, if the character $S[i]$ does NOT exist next at the Active Point, we split the active edge (if $\text{active\_len} > 0$) to create a new internal node $w$, attach a new leaf $[i, \infty)$ for $S[i]$, wire the previous internal node created in this phase to $w$ via a Suffix Link $\text{link}[u] = w$, decrement $\text{rem}$, and advance the Active Point to the next shorter suffix via $\text{link}[\text{active\_node}]$.
3. Rule 3 (Already Present — Showstopper): If character $S[i]$ ALREADY exists at the Active Point, we simply advance $\text{active\_len}$ by $1$ (canonicalizing across internal nodes via the skip/count trick) and break out of phase $i$ immediately! Why? Because if the longest unbranched suffix $S[j..i]$ is already in the tree, every shorter suffix $S[j+1..i], \dots, S[i..i]$ is also already in the tree.

3. Visual Trace: Suffix Tree & Suffix Links for $S = \texttt{"xabxa\$"}$

4. Production Implementation: Ukkonen's Online $O(N)$ Suffix Tree

#include <map>
#include <string>
#include <string_view>
#include <vector>

class UkkonenSuffixTree {
public:
    static constexpr int INF = 1e9;
    struct Node {
        int l = 0, r = 0; // Edge label S[l .. min(r, current_end)]
        int link = 0;     // Suffix link to shorter suffix internal node
        std::map<char, int> next;
        int edge_len(int pos) const { return std::min(r, pos + 1) - l; }
    };

    explicit UkkonenSuffixTree(std::string_view str) : s_(str) {
        nodes_.emplace_back(); // Node 0 = root
        for (int i = 0; i < static_cast<int>(s_.size()); ++i) {
            extend(i);
        }
    }

    // Returns true iff pattern P is a substring of S in O(|P| log |Sigma|) time
    bool contains(std::string_view pat) const {
        int u = 0, n = static_cast<int>(s_.size());
        size_t idx = 0;
        while (idx < pat.size()) {
            auto it = nodes_[u].next.find(pat[idx]);
            if (it == nodes_[u].next.end()) return false;
            int v = it->second;
            int len = nodes_[v].edge_len(n - 1);
            for (int k = 0; k < len && idx < pat.size(); ++k, ++idx) {
                if (s_[nodes_[v].l + k] != pat[idx]) return false;
            }
            u = v;
        }
        return true;
    }

private:
    std::string s_;
    std::vector<Node> nodes_;
    int active_node_ = 0, active_edge_ = 0, active_len_ = 0, rem_ = 0;

    int new_node(int l, int r) {
        nodes_.push_back(Node{l, r, 0, {}});
        return static_cast<int>(nodes_.size()) - 1;
    }

    void extend(int pos) {
        ++rem_;
        int last_created = 0;
        while (rem_ > 0) {
            if (active_len_ == 0) active_edge_ = pos;
            auto it = nodes_[active_node_].next.find(s_[active_edge_]);
            if (it == nodes_[active_node_].next.end()) {
                // Rule 2 at an explicit node: attach leaf directly
                nodes_[active_node_].next[s_[active_edge_]] = new_node(pos, INF);
                if (last_created != 0) {
                    nodes_[last_created].link = active_node_;
                    last_created = 0;
                }
            } else {
                int nxt = it->second;
                int len = nodes_[nxt].edge_len(pos);
                // Skip/Count Trick: hop across entire edge if active_len_ >= len
                if (active_len_ >= len) {
                    active_edge_ += len;
                    active_len_ -= len;
                    active_node_ = nxt;
                    continue;
                }
                // Rule 3 (Showstopper): character s_[pos] already on edge
                if (s_[nodes_[nxt].l + active_len_] == s_[pos]) {
                    if (last_created != 0 && active_node_ != 0) {
                        nodes_[last_created].link = active_node_;
                    }
                    ++active_len_;
                    break;
                }
                // Rule 2 inside an edge: split edge at split and attach leaf
                int split = new_node(nodes_[nxt].l, nodes_[nxt].l + active_len_);
                nodes_[active_node_].next[s_[active_edge_]] = split;
                nodes_[split].next[s_[pos]] = new_node(pos, INF);
                nodes_[nxt].l += active_len_;
                nodes_[split].next[s_[nodes_[nxt].l]] = nxt;
                if (last_created != 0) nodes_[last_created].link = split;
                last_created = split;
            }
            --rem_;
            if (active_node_ == 0 && active_len_ > 0) {
                --active_len_;
                active_edge_ = pos - rem_ + 1;
            } else if (active_node_ != 0) {
                active_node_ = nodes_[active_node_].link;
            }
        }
    }
};