很多字符串挤在一起，公共前缀被反复存了很多遍——Trie 把这些公共前缀合并成共享的树枝，查询只和字符串长度有关，和字符串总数无关。
如果有一个包含很多单词的词典，需要频繁判断"某个字符串是不是词典里的一个单词"或者"某个字符串是不是词典里某个单词的前缀"——如果把单词逐个存成普通字符串列表，每次查询都要挨个比较，效率和单词总数、单词长度都有关。
Trie（字典树 / 前缀树）把所有单词的公共前缀合并存储成一棵树，之后每次查询只需要沿着树"走"一遍待查字符串的长度那么多步，和词典里到底有多少个单词完全无关。
Trie 是一棵树：根节点代表"空字符串"，从根节点出发的每一条边对应一个字符，从根走到某个节点所经过的字符连起来，就是该节点代表的一段前缀。如果两个单词有相同的前缀，它们在 Trie 里会共用从根节点开始的这一段路径，只在前缀分叉的地方才各自延伸出不同的树枝。每个节点还需要一个标记，记录"走到这里，是否恰好构成一个完整的单词"（因为一个单词的路径，可能正好是另一个更长单词路径的前半段）。
依次插入 "cat"、"car"、"do"、"dog" 这 4 个单词：
"cat" 和 "car" 共用了 c→a 这一段公共前缀，只在第三个字符分叉成 t 和 r 两条树枝。更值得注意的是 "do" 和 "dog"："do" 本身是一个完整单词（o 节点带 ★），但它同时也是 "dog" 的前缀，所以这个节点既标记了 ★，又继续往下延伸了一条树枝到 g。这正是"完整单词"和"只是路径存在"必须分开判断的原因（见 ⑥ 陷阱）。竞赛中通常用静态数组模拟树形结构（避免频繁 new 动态节点的开销），trie[cur][c] 表示节点 cur 沿着字符 c 这条边走到的下一个节点编号，0 表示"这条边不存在"：
| 1 | int trie[MAXN][26], cnt; // trie[cur][c]：节点 cur 沿字符 c 走到的节点编号；cnt：已用节点数 |
| 2 | bool isEnd[MAXN]; // isEnd[node]：走到 node 是否恰好是一个完整单词 |
| 3 | |
| 4 | void Insert(const string& word) |
| 5 | { |
| 6 | int cur = 0; // 0 号节点是根节点 |
| 7 | for (char c : word) |
| 8 | { |
| 9 | int idx = c - 'a'; |
| 10 | if (!trie[cur][idx]) trie[cur][idx] = ++cnt; // ★ 这条边不存在就新建一个节点 |
| 11 | cur = trie[cur][idx]; // 沿着这条边走过去 |
| 12 | } |
| 13 | isEnd[cur] = true; // 单词插入完毕，标记终点 |
| 14 | } |
| 15 | |
| 16 | bool Search(const string& word) // 词典里是否存在这个完整单词 |
| 17 | { |
| 18 | int cur = 0; |
| 19 | for (char c : word) |
| 20 | { |
| 21 | int idx = c - 'a'; |
| 22 | if (!trie[cur][idx]) return false; // 路径都走不通，一定不存在 |
| 23 | cur = trie[cur][idx]; |
| 24 | } |
| 25 | return isEnd[cur]; // ★ 路径走通了，还要看这里是不是一个"完整单词"的终点 |
| 26 | } |
| 27 | |
| 28 | bool StartsWith(const string& prefix) // 词典里是否存在以 prefix 为前缀的单词 |
| 29 | { |
| 30 | int cur = 0; |
| 31 | for (char c : prefix) |
| 32 | { |
| 33 | int idx = c - 'a'; |
| 34 | if (!trie[cur][idx]) return false; |
| 35 | cur = trie[cur][idx]; |
| 36 | } |
| 37 | return true; // ★ 只要路径存在就够了，不需要看 isEnd |
| 38 | } |
Search 和 StartsWith 几乎是同一份代码，只差最后一行：Search 要求走到的节点必须恰好是某个单词的终点（isEnd 为真）；StartsWith 只要求路径能走通，不关心走到的节点是不是某个单词的终点——这正对应 ③ 图解里 "do" 和 "dog" 的区别：查询前缀 "do" 应该返回 true（路径存在），但查询完整单词时，"do" 是词典里的词，"dog" 也是，两者都能在 isEnd 上得到确认。插入或查询一个长度为 L 的字符串，只需要沿着树走 L 步，每一步是 O(1)（数组下标访问），所以单次操作是 O(L)——和词典里已经存了多少个单词完全无关。空间上，最坏情况下（所有单词没有公共前缀）需要的节点数是所有单词长度之和。
"do" 这个单词时，路径 root→d→o 确实存在（因为 "dog" 也经过这里），但如果词典里只插入了 "dog"，没有插入 "do"，此时 isEnd[o节点] 是 false——查询完整单词 "do" 应该返回不存在，必须依赖 isEnd 判断，不能只看路径能不能走通。MAXN 开得不够：节点总数最坏情况下等于所有插入单词的长度之和（而不是单词的个数），如果词典很大且单词之间几乎没有公共前缀，需要的节点数会接近这个总长度，数组开小了会越界。26 个），如果需要支持大小写字母、数字甚至更大的字符集，trie[MAXN][26] 这种固定大小的写法会浪费大量内存（大部分子节点其实是空的）。这种情况下可以考虑用 map 或 unordered_map 代替固定大小的数组存边，用空间换取灵活性，但访问速度会比数组慢一些。O(1) 的数字比较；KMP 解决"一个模式串在文本里的所有出现位置"；Trie 解决"很多字符串共享前缀"的场景，让前缀相关的查询和字符串总数无关。三者经常配合其他数据结构（比如 Trie 常和 DFS、动态规划结合）解决更复杂的字符串问题。