ARTICLE · 1385580
字典树——模板 Trie
一、什么是字典树
字典树(Trie),又叫前缀树,是一种专门用来处理字符串集合的树形数据结构。
它的核心思想很简单:把字符串一个字符一个字符地挂在树上,公共前缀只存一次。
有了这棵树,我们能很快做三件事:
插入一个字符串;
查询某个字符串是否出现过;
查询有多少个字符串以某个前缀开头。
二、字典树的核心功能
1. 节点长什么样
字典树上的每个节点代表"某个前缀",它需要存以下信息:
它往下连的子节点(用
char → node*的映射表示,走到哪个字符就跳到哪个子节点);一个
isEnd标记,表示"有没有单词在这里结束";本题再加一个
cnt,表示"有多少个单词经过这个节点"。
cnt 是本题的关键。有了它,前缀查询就不用再往下遍历整棵子树,直接读节点上的 cnt 就行。
2. 插入(insert)
从根节点开始,一个字符一个字符往下走:
如果当前字符对应的子节点不存在,就新建一个;
然后走到这个子节点,把它的
cnt加 1;走完整串后,把最后一个节点标记为
isEnd = true。
注意:cnt 加 1 的位置要放在跳到子节点之后,而不是新建节点的时候。这样哪怕是终点节点也会被计数。
3. 查找节点(findNode)
从根节点往下走,如果某个字符对应的子节点不存在,说明整棵树里没有这个前缀,返回空指针;否则一路走到最后一个字符,返回那个节点。
这个函数是单词查询、前缀查询的"公共底盘"。
4. 单词查询(search)
先找到单词的终点节点,再看它的 isEnd 是否为真。为真说明这个单词确实被插入过,否则只是某个更长单词的前缀。
5. 前缀查询(startWith)
先找到前缀的终点节点。如果节点不存在,返回 0;如果存在,直接返回它的 cnt。
比如插入 fusu 和 fusufusu 后,节点 fusu 的 cnt 是 2,所以查询前缀 fusu 就返回 2。
三、结合本题的思路
题目要求:给定 n 个模式串和 q 次询问,每次给一个文本串 t,问有多少个模式串以 t 为前缀。
思路很直接:
把所有模式串插入字典树,插入时沿途给每个节点的
cnt加 1;对每次询问,用
findNode找到 t 的终点节点;如果节点不存在,输出 0;如果存在,输出它的
cnt。
两点细节:
题目里重复出现的模式串要分别计数(因为问的是"有多少个字符串 s_j"),所以不需要去重,
cnt直接累加就好;字符串总长最多 3×10⁶,字符集包含大小写字母和数字,用
unordered_map<char, node*>比较通用。
四、参考代码
#include<bits/stdc++.h>using namespace std;struct node {unordered_map<char, node*> child; // 子节点:字符 -> 子节点指针bool isEnd; // 是否有单词在此结束int cnt; // 经过当前节点的单词数node() : isEnd(false), cnt(0) {}};// 插入一个单词,沿途维护 cntvoidinsert(node* root, const string& word){node* cur = root;for (char c : word) {if (cur->child.find(c) == cur->child.end())cur->child[c] = new node();cur = cur->child[c];++cur->cnt; // 走到这个节点,计数加一}cur->isEnd = true;}// 找到字符串终点对应的节点,不存在返回 nullptrnode* findNode(node* root, const string& str){node* cur = root;for (char c : str) {auto it = cur->child.find(c);if (it == cur->child.end()) return nullptr;cur = it->second;}return cur;}// 单词查询:判断某个单词是否被完整插入过boolsearch(node* root, const string& word){node* p = findNode(root, word);return p && p->isEnd;}// 前缀查询:返回以 pre 为前缀的单词数intstartWith(node* root, const string& pre){node* p = findNode(root, pre);return p ? p->cnt : 0;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int T, n, q;string s;cin >> T;while (T--) {cin >> n >> q;node* root = new node();while (n--) { cin >> s; insert(root, s); } // 插入全部模式串while (q--) { cin >> s; cout << startWith(root, s) << '\n'; } // 逐次查询}return 0;}
五、几个容易踩的坑
cnt加 1 的位置:必须放在"跳到子节点之后"。如果放在"新建节点时加 1",那所有复用的旧路径都不会计数,答案会偏小。别用
child.size()当作前缀数量:child.size()只是"直接子节点个数"。比如只插入abc,查前缀abc时终点节点没有子节点,size()是 0,但正确答案是 1。isEnd和cnt分工不同:isEnd管"这个单词是否存在",cnt管"有多少单词以这段为前缀"。两者别混用。















































































