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.
| Operation | Complexity |
|---|---|
| Access | O(m) |
| Search | O(m) |
| Insertion | O(n) build (Ukkonen) |
| Deletion | O(n) |
| Space | O(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 andlt; n$ internal nodes!Loading AntInLoop...
- 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.