Trie and Compressed Trie

The string-branch view of the trie: what it is good for in string problems, and how compression turns it into a suffix tree.

Plain trie

One node per distinct prefix of the stored set. Insertion and lookup are $O(|w|)$, independent of how many words are stored. See Trie for the implementation.

Size: $O(\sum |w_i|)$ nodes — one per distinct prefix. Storing all $n$ suffixes of a string gives $O(n^2)$ nodes, which is why plain tries do not scale to substring problems.

Compressed trie (radix tree / Patricia trie)

Merge every chain of single-child nodes into one edge labelled with a substring.

plain trie of {test, team, toast}     compressed
        t                                  t
        |                                / | \
        e --- s --- t                 e**  oast
       / \                           /  \
      a   s                        st    am

• Node count drops from $O(\sum |w|)$ to $O(\text{number of words})$ — at most $2k-1$ nodes for $k$ words.
• Edge labels are stored as (start, end) index pairs into the original text, so the memory stays $O(k)$ regardless of word length.
• Insertion may need to split an edge, which is the only added complexity.

The compressed trie of all suffixes of a string is precisely the suffix tree.

That identity is the bridge from tries to the suffix-structure world: $O(n^2)$ nodes become $O(n)$ purely through compression.

String problems a trie solves

Problem	Method
Autocomplete / prefix search	descend to the prefix node, enumerate its subtree
Count words with a given prefix	a cnt field per node
Longest common prefix of a set	descend while there is exactly one child
Longest prefix of $w$ that is a stored word	descend, remembering the last word-end
Word break / segmentation DP	trie walk from each position
Sort strings lexicographically	DFS the trie — a radix sort in disguise
$k$-th lexicographic word	descend using subtree counts
Maximum XOR pair	binary trie
Multi-pattern matching	Aho-Corasick = trie + suffix links

Word break with a trie

// dp[i] = can s[0..i) be split into dictionary words?
vector<bool> dp(n + 1, false); dp[0] = true;
for (int i = 0; i < n; i++) {
    if (!dp[i]) continue;
    int v = 0;
    for (int j = i; j < n; j++) {
        v = trie.nxt[v][s[j] - 'a'];
        if (v == -1) break;
        if (trie.isEnd[v]) dp[j + 1] = true;
    }
}

$O(n^2)$ worst case but with an early exit that makes it near-linear on real dictionaries — and far better than trying every substring against a hash set.

Memory: the practical constraint

Children representation	Lookup	Memory per node
array<int, 26>	$O(1)$	104 bytes
map<char,int>	$O(\log \sigma )$	~48 bytes + overhead
sorted vector<pair<char,int>>	$O(\log \sigma )$	~8 bytes per child
bitmask + packed children	$O(1)$ with popcount	~12 bytes

For $10^6$ total characters over a 26-letter alphabet, the array version is 104 MB — usually over the limit. The sorted-vector version is typically the right compromise.

The trie family

Structure	Is	Use
Trie	prefix tree	dictionaries, prefixes
Compressed trie	trie with merged chains	space-efficient dictionaries
Suffix tree	compressed trie of all suffixes	all substrings
Binary trie	trie over bits	XOR problems
Aho-Corasick	trie + failure links	multi-pattern matching
Suffix automaton	a DAG, not a tree	all substrings, minimal size
DAWG	minimised trie of a word set	dictionary compression

Persistent tries

Making a trie persistent (copy the $O(|w|)$ nodes on the insertion path) gives versioned dictionaries and, for binary tries, “maximum XOR over an index range” — one of the most useful applications of persistence in competitive programming.

See also: Trie · Suffix Tree · Aho-Corasick