AntInLoop

Suffix Tree Data Structure Data Structure

A Suffix Tree is a compressed Trie of all suffixes of a string, built in linear O(n) time via Ukkonen's algorithm to answer pattern matching and repeated substring queries in O(m) time.

OperationComplexity
AccessO(m)
SearchO(m)
InsertionO(n) build (Ukkonen)
DeletionO(n)
SpaceO(n)

Interactive Visualizer · C++ / Python / Java / JS Code

Suffix Tree Data Structure

A Suffix Tree of a string $S$ (appended with a unique terminal sentinel $) is the compressed Trie containing every suffix of $S$. Because chains of single-child nodes are compressed into edges labeled by (start, length) slices of $S$, the tree has at most $2n$ nodes and $O(n)$ total space—and can be built online in $O(n)$ time using Ukkonen's Algorithm!

At a Glance

| Operation | Complexity |

| :--- | :---: |

| Build (Ukkonen's Algorithm) | $O(n)$ |

| Substring Search (pattern length $m$) | $O(m)$ (independent of $n$!) |

| Longest Repeated Substring | $O(n)$ (deepest internal node) |

| Auxiliary Space | $O(n)$ (high constant factor; prefer Suffix Array when RAM is tight) |

---

Key Structural Insights

  • Why Compression Matters: An uncompressed Suffix Trie has $O(n^2)$ nodes (e.g., "abcde..."). Compressing unary paths to (start, len) edge slices reduces it to $\le n$ leaves and

    Loading AntInLoop...

    lt; n$ internal nodes!
  • Deepest Internal Node = Longest Repeated Substring: Every internal node has $\ge 2$ leaves in its subtree, meaning the string spelled from root to that internal node occurs at least twice!
  • Suffix Tree vs. Suffix Array vs. Suffix Automaton:
  • Suffix Tree: Best conceptual model and $O(m)$ search, but heaviest in memory.
  • Suffix Array + LCP: ~10× less memory, simpler to code ($O(n \log n)$ build).
  • Suffix Automaton: Linear $O(n)$ build, compact, easiest for online distinct substring & LCS problems.

---

Practice Problems

Easy

1. Ukkonen's $O(n)$ Suffix Tree Construction & $O(m)$ Substring Search

Build a Suffix Tree online in $O(n)$ time using Ukkonen's Algorithm and check if query patterns exist in $O(m)$ time.

Approach: Maintain the active point (activeNode, activeEdge, activeLen), remainder count, global leaf end pointer, and suffix links. Every phase amortizes to $O(1)$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

struct SuffixTree {
    struct Node {
        int start, end, link = 0;
        std::map<char, int> next;
        Node(int s, int e) : start(s), end(e) {}
    };

    std::string s;
    std::vector<Node> nodes;
    int activeNode = 0, activeEdge = 0, activeLen = 0, remainder = 0;
    static constexpr int INF = 1'000'000'000;

    explicit SuffixTree(std::string str) {
        s = std::move(str) + '
      

Loading AntInLoop...

#39;; nodes.emplace_back(-1, -1); for (int i = 0; i < static_cast<int>(s.size()); ++i) extend(i); } int edgeLen(int node, int pos) const { return std::min(nodes[node].end, pos + 1) - nodes[node].start; } void extend(int pos) { ++remainder; int lastCreated = -1; while (remainder > 0) { if (activeLen == 0) activeEdge = pos; char ch = s[activeEdge]; auto it = nodes[activeNode].next.find(ch); if (it == nodes[activeNode].next.end()) { int leaf = static_cast<int>(nodes.size()); nodes.emplace_back(pos, INF); nodes[activeNode].next[ch] = leaf; if (lastCreated != -1) { nodes[lastCreated].link = activeNode; lastCreated = -1; } } else { int nxt = it->second; int len = edgeLen(nxt, pos); if (activeLen >= len) { activeEdge += len; activeLen -= len; activeNode = nxt; continue; } if (s[nodes[nxt].start + activeLen] == s[pos]) { ++activeLen; if (lastCreated != -1 && activeNode != 0) nodes[lastCreated].link = activeNode; break; } int split = static_cast<int>(nodes.size()); nodes.emplace_back(nodes[nxt].start, nodes[nxt].start + activeLen); nodes[activeNode].next[ch] = split; int leaf = static_cast<int>(nodes.size()); nodes.emplace_back(pos, INF); nodes[split].next[s[pos]] = leaf; nodes[nxt].start += activeLen; nodes[split].next[s[nodes[nxt].start]] = nxt; if (lastCreated != -1) nodes[lastCreated].link = split; lastCreated = split; } --remainder; if (activeNode == 0 && activeLen > 0) { --activeLen; activeEdge = pos - remainder + 1; } else if (activeNode != 0) activeNode = nodes[activeNode].link; } } bool contains(const std::string& pat) const { int node = 0, i = 0, n = static_cast<int>(pat.size()), textLen = static_cast<int>(s.size()); while (i < n) { auto it = nodes[node].next.find(pat[i]); if (it == nodes[node].next.end()) return false; int nxt = it->second; int len = std::min(nodes[nxt].end, textLen) - nodes[nxt].start; for (int k = 0; k < len && i < n; ++k, ++i) { if (s[nodes[nxt].start + k] != pat[i]) return false; } node = nxt; } return true; } }; int main() { SuffixTree st("abracadabra"); std::cout << std::boolalpha << st.contains("cadab") << " " << st.contains("abra") << " " << st.contains("xyz") << "\n"; // true true false return 0; }

</details>

2. Longest Repeated Substring via Suffix Tree DFS ($O(n)$)

Find the longest substring that occurs at least twice by finding the deepest internal node in the Suffix Tree.

Approach: Any node with $\ge 2$ children is an internal node representing a repeated substring. DFS tracking string depth returns the longest repeated substring in $O(n)$!

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

struct SuffixTreeLRS {
    struct Node {
        int start, end, link = 0;
        std::map<char, int> next;
        Node(int s, int e) : start(s), end(e) {}
    };
    std::string s;
    std::vector<Node> nodes;
    int activeNode = 0, activeEdge = 0, activeLen = 0, remainder = 0;
    static constexpr int INF = 1'000'000'000;

    explicit SuffixTreeLRS(std::string str) {
        s = std::move(str) + '
      

Loading AntInLoop...

#39;; nodes.emplace_back(-1, -1); for (int i = 0; i < static_cast<int>(s.size()); ++i) extend(i); } int edgeLen(int node, int pos) const { return std::min(nodes[node].end, pos + 1) - nodes[node].start; } void extend(int pos) { ++remainder; int last = -1; while (remainder > 0) { if (activeLen == 0) activeEdge = pos; char ch = s[activeEdge]; auto it = nodes[activeNode].next.find(ch); if (it == nodes[activeNode].next.end()) { int leaf = static_cast<int>(nodes.size()); nodes.emplace_back(pos, INF); nodes[activeNode].next[ch] = leaf; if (last != -1) { nodes[last].link = activeNode; last = -1; } } else { int nxt = it->second, len = edgeLen(nxt, pos); if (activeLen >= len) { activeEdge += len; activeLen -= len; activeNode = nxt; continue; } if (s[nodes[nxt].start + activeLen] == s[pos]) { ++activeLen; if (last != -1 && activeNode != 0) nodes[last].link = activeNode; break; } int split = static_cast<int>(nodes.size()); nodes.emplace_back(nodes[nxt].start, nodes[nxt].start + activeLen); nodes[activeNode].next[ch] = split; int leaf = static_cast<int>(nodes.size()); nodes.emplace_back(pos, INF); nodes[split].next[s[pos]] = leaf; nodes[nxt].start += activeLen; nodes[split].next[s[nodes[nxt].start]] = nxt; if (last != -1) nodes[last].link = split; last = split; } --remainder; if (activeNode == 0 && activeLen > 0) { --activeLen; activeEdge = pos - remainder + 1; } else if (activeNode != 0) activeNode = nodes[activeNode].link; } } std::string longestRepeated() const { int bestLen = 0, bestEnd = 0; auto dfs = [&](auto& self, int u, int depth) -> void { if (u != 0 && !nodes[u].next.empty() && depth > bestLen) { bestLen = depth; bestEnd = nodes[u].end; } for (const auto& [ch, v] : nodes[u].next) { if (!nodes[v].next.empty()) { self(self, v, depth + (nodes[v].end - nodes[v].start)); } } }; dfs(dfs, 0, 0); return bestLen == 0 ? "" : s.substr(bestEnd - bestLen, bestLen); } }; int main() { SuffixTreeLRS st("banana"); std::cout << st.longestRepeated() << "\n"; // ana return 0; }

</details>

---

Related Structures & Algorithms

  • Suffix Array — memory-efficient sorted-array equivalent of a Suffix Tree.
  • Suffix Automaton — compact linear-time substring automaton.
  • Trie — prefix tree for a dictionary of strings.