Trie
进阶Trie 用路径表示字符串，前缀天然共享。
// 算法讲解
Trie
输入一组共享前缀的单词，可以直观看到前缀是如何被复用的。
待机
速度 中
待机 ⌨1struct TrieNode {
2 int next[26];
3 bool end;
4 TrieNode() : end(false) {
5 memset(next, -1, sizeof(next));
6 }
7};
8
9vector<TrieNode> trie(1);
10
11void insertWord(const string& s) {
12 int node = 0;
13 for (char ch : s) {
14 int c = ch - 'a';
15 if (trie[node].next[c] == -1) {
16 trie[node].next[c] = trie.size();
17 trie.emplace_back();
18 }
19 node = trie[node].next[c];
20 }
21 trie[node].end = true;
22}
复杂度分析
时间 按串长 O(L)
空间 O(字符总数)
最优 O(1) 空串
最坏 O(L)
算法讲解
Trie 的每条从根到节点的路径都对应一个前缀，因此插入和查询都按字符逐层向下走。
它特别适合前缀匹配、词频统计、自动补全和敏感词过滤。
和哈希表相比，Trie 把"相同前缀"合并存储，所以在大量前缀重复时很有优势。
进一步叠加 fail 指针后，就能过渡到 AC 自动机。