Trie
Store strings by prefix so inserts, prefix checks, and dictionary transitions depend on length rather than set size.
Trie
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
A trie stores strings by their prefixes. Instead of comparing one full string against many others, I walk character by character through shared nodes. That makes tries a natural fit for dictionary problems, prefix queries, and some automaton constructions.
When to Use It
Use a trie when:
the main queries are by prefix,
the alphabet is small enough to store transitions directly,
many strings share prefixes and you want to reuse that structure.
Core Idea
Each edge corresponds to one character, and each root-to-node path represents a prefix. Full words are marked with an end flag or a terminal counter.
Because the path length equals the string length, operations depend on the string size rather than the number of stored strings.
Key Insight
The trie is valuable when the query is ``what happens after this prefix?'' If the problem is only about exact whole-word lookup, a hash table is usually simpler. The structure pays for itself when prefix sharing matters.
Operations / Main Technique
insert a word,
test whether a word exists,
test whether a prefix exists,
count how many words pass through a prefix node.
Worked example.
If the set contains \(\texttt{car}\), \(\texttt{card}\), and \(\texttt{care}\), then the path for \(\texttt{car}\) is shared and branches only afterward.
Correctness Intuition
Each inserted character follows or creates the unique outgoing edge for that symbol, so the path stored in the trie is exactly the word itself. Shared prefixes meet at shared nodes, and different next characters diverge into different children.
Complexity Analysis
For word length \(L\):
insert: \(O(L)\),
contains: \(O(L)\),
prefix query: \(O(L)\).
Implementation
The sample code uses a lowercase English alphabet trie with:
a terminal counter,
a pass-through counter,
insert, exact lookup, and prefix counting.
Common Pitfalls
Using a trie when the alphabet is huge and sparse.
Forgetting whether repeated insertions should be allowed or counted.
Confusing ``prefix exists'' with ``full word exists''.
Spending too much memory on a static array when a compressed representation would be better.
Variants / Extensions
Binary trie for XOR problems.
Aho-Corasick, which augments the trie with failure links.
Compressed trie or radix tree for memory-sensitive settings.
Practice Problems
Prefix dictionary queries.
Count how many stored words share a given prefix.
Maximum XOR using a binary trie.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Trie {
struct Node {
array<int, 26> next{};
int terminal = 0;
int pass = 0;
Node() {
next.fill(-1);
}
};
vector<Node> nodes;
Trie() : nodes(1) {}
void insert(const string& s) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (nodes[v].next[c] == -1) {
nodes[v].next[c] = (int)nodes.size();
nodes.push_back(Node{});
}
v = nodes[v].next[c];
++nodes[v].pass;
}
++nodes[v].terminal;
}
bool contains(const string& s) const {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (nodes[v].next[c] == -1) {
return false;
}
v = nodes[v].next[c];
}
return nodes[v].terminal > 0;
}
int count_with_prefix(const string& s) const {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (nodes[v].next[c] == -1) {
return 0;
}
v = nodes[v].next[c];
}
return nodes[v].pass;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.