viii. Suffix Tree

The compressed trie of all suffixes of s\$$ (a unique sentinel keeps every suffix a leaf): n + 1$leaves,atmost$n$internalnodes,eachwith$\ge 2$children;edgesarelabelledbyindexpairs$(l, r)$,sothetreeis$O(n)$despiterepresenting$O(n^2)$ substrings. Every substring is a root path, so many questions become tree navigation. In contests prefer the suffix automaton (its link tree is the suffix tree of the reversed string) or SA + LCP (the LCP interval tree below); Ukkonen is here for completeness and tested.

Question	Method	Cost
is $t$ a substring; occurrences of $t$	walk from the root; leaves under the arrival point	$O(|t|)$ ($+$ output)
longest repeated substring	deepest internal node	$O(n)$
distinct substrings of $s$	sum of edge lengths of the tree of s\$$ minus the n + 1$stringscontaining$$$	$O(n)$
longest common substring of $k$ strings	generalised tree (distinct separators); deepest node with leaves of every colour	$O(n)$
longest palindromic substring	generalised tree of $s$ and $\mathrm{rev}(s)$ + LCA	$O(n)$
maximal repeats; tandem repeats	internal nodes with left-diverse leaves; Gusfield–Stoye	$O(n)$
longest common extension	LCA of two leaves	$O(1)$ after $O(n)$
matching statistics	one walk with suffix links	$O(m)$

Construction	Direction	Online	Note
Weiner (1973)	right to left	prepend	$O(n\sigma )$ memory
McCreight (1976)	longest to shortest suffix	no	hard
Ukkonen (1995)	left to right	append	most taught; fiddly
Farach (1997)	divide and conquer	no	integer alphabets, theoretical
from SA + LCP		no	easy: monotonic stack

	suffix tree	suffix array	suffix automaton
nodes	$\le 2n$	$n$ integers	$\le 2n$
memory constant	high ($\sigma$ per node)	lowest	medium
build difficulty	hardest	easy	easiest
online	Ukkonen only	no	yes
lexicographic order	yes	natural	needs work
all substrings	yes	via LCP intervals	natural

Ukkonen. Phase $i$ extends the implicit tree of $s[\mathrm{0..}i)$ to $s[\mathrm{0..}i]$. Three tricks make it linear: edge-label compression with leaf edges ending at a shared “current end” (extending all leaves is free: rule 1); suffix links from the node of $x\alpha$ to the node of $\alpha$, so the next insertion point is reached in amortised $O(1)$; rule 3 (“showstopper”): if the next character already follows the current point, it follows every shorter suffix too, so the phase stops. The active point encodes where the next insertion goes.

struct SuffixTree {                                         // Ukkonen; edges [l, r) into s; append a unique sentinel yourself
    struct Node { int l, r, par, link; map<char, int> nxt; Node(int l = 0, int r = 0, int p = -1) : l(l), r(r), par(p), link(-1) {} int len() const { return r - l; } };
    string s; int n; vector<Node> t; pair<int, int> ptr{0, 0};   // (node, position on the edge into node)
    int child(int v, char c) { auto it = t[v].nxt.find(c); return it == t[v].nxt.end() ? -1 : it->second; }
    pair<int, int> go(pair<int, int> st, int l, int r) {    // walk down by s[l, r) from state st; {-1,-1} if impossible
        while (l < r) {
            if (st.second == t[st.first].len()) { int v = child(st.first, s[l]); if (v == -1) return {-1, -1}; st = {v, 0}; }
            else {
                if (s[t[st.first].l + st.second] != s[l]) return {-1, -1};
                if (r - l < t[st.first].len() - st.second) return {st.first, st.second + r - l};
                l += t[st.first].len() - st.second; st.second = t[st.first].len();
            }
        }
        return st;
    }
    int split(pair<int, int> st) {                          // make the point explicit, return its node
        auto [v, pos] = st;
        if (pos == t[v].len()) return v;
        if (pos == 0) return t[v].par;
        Node old = t[v]; int id = sz(t); t.push_back(Node(old.l, old.l + pos, old.par));
        t[old.par].nxt[s[old.l]] = id; t[id].nxt[s[old.l + pos]] = v;
        t[v].par = id; t[v].l += pos;
        return id;
    }
    int getLink(int v) {
        if (t[v].link != -1) return t[v].link;
        if (t[v].par == -1) return 0;
        int to = getLink(t[v].par);
        return t[v].link = split(go({to, t[to].len()}, t[v].l + (t[v].par == 0), t[v].r));
    }
    void extend(int pos) {
        while (true) {
            auto np = go(ptr, pos, pos + 1);
            if (np.first != -1) { ptr = np; return; }       // rule 3
            int mid = split(ptr), leaf = sz(t); t.push_back(Node(pos, n, mid)); t[mid].nxt[s[pos]] = leaf;
            ptr.first = getLink(mid); ptr.second = t[ptr.first].len();
            if (!mid) break;
        }
    }
    SuffixTree(const string& str) : s(str), n(sz(str)) { t.push_back(Node()); for (int i = 0; i < n; i++) extend(i); }
    ll distinctSubstringsWithSentinel() const { ll r = 0; for (int v = 1; v < sz(t); v++) r += t[v].len(); return r; }
    int countOccurrences(const string& p) {                 // leaves below the locus of p
        pair<int, int> cur = {0, 0};
        for (char ch : p) {
            if (cur.second == t[cur.first].len()) { int u = child(cur.first, ch); if (u == -1) return 0; cur = {u, 1}; }
            else { if (s[t[cur.first].l + cur.second] != ch) return 0; cur.second++; }
        }
        vector<int> stck = {cur.first}; int leaves = 0;
        while (!stck.empty()) { int u = stck.back(); stck.pop_back(); if (t[u].nxt.empty()) leaves++; for (auto& [c, w] : t[u].nxt) stck.push_back(w); }
        return leaves;
    }
};
 
vector<array<int, 3>> lcpIntervals(const vector<int>& lcp) {   // (depth, lb, rb) of every internal node, lcp from kasai (lcp[0] = 0)
    int n = sz(lcp); vector<array<int, 3>> res; vector<pair<int, int>> st = {{0, 0}};   // (depth, lb)
    for (int i = 1; i <= n; i++) {
        int cur = i < n ? lcp[i] : 0, lb = i - 1;
        while (st.back().first > cur) { auto [d, l] = st.back(); st.pop_back(); res.push_back({d, l, i - 1}); lb = l; }
        if (st.back().first < cur) st.push_back({cur, lb});
    }
    res.push_back({0, 0, n - 1});                           // the root
    return res;
}

Proof: Ukkonen's invariants and the LCP interval tree

Ukkonen. Invariant: after phase $i$, the tree is the implicit suffix tree of $s[\mathrm{0..}i]$ and ptr is the locus of the longest suffix of $s[\mathrm{0..}i]$ that occurs at least twice (the active point). In phase $i+1$, suffixes longer than the active one end at leaves and are extended by the open leaf ends (rule 1). Starting from the active point, if $s_{i+1}$ already continues it, the same holds for all shorter suffixes (they are suffixes of a string followed by $s_{i+1}$), so the phase ends (rule 3, with the active point moved). Otherwise the point is made explicit (split), a leaf is attached (rule 2), and the next shorter suffix is reached via the suffix link of the split node (computed lazily: the link of a node is the locus of its string without the first character, found from the parent’s link by walking down the edge label, the skip-count walk go). Linearity: every leaf is created once ($\le n$ rule-2 steps in total), the depth of the active point grows by at most one per phase, and each suffix-link hop decreases it while walking down edges skips whole edges, so the total work is $O(n)$ for a constant alphabet ($O(n\log \sigma )$ with map). Counts: with the unique sentinel every suffix ends at a leaf, so the leaves below the locus of $p$ are its occurrences; the edge lengths sum to the number of distinct substrings of s\$$, of which exactly n + 1$(thesuffixesof$s$$)contain$$$.

LCP intervals. An internal node of string depth $\ell$ corresponds to a maximal SA interval $[lb,rb]$ of suffixes sharing a prefix of length $\ell$, with $\min \mathrm{lcp}(lb,rb]=\ell$ and boundaries strictly smaller. Scanning the lcp values left to right with a stack of open intervals (strictly increasing depths), a value smaller than the top closes that interval at $i-1$ (its right boundary is where the common prefix breaks), and the closed interval’s left boundary becomes that of the next interval opened at the new depth. Each interval is pushed and popped once: $O(n)$; the root $[0,n-1]$ has depth 0. Checked: Ukkonen’s internal node count and distinct substrings against brute force, occurrence counts against find, and the LCP intervals against the right-branching substrings computed by brute force.

Related notes

• Suffix Automaton
• Suffix Array
• Theoretical Algorithms (Weiner, McCreight, Farach)