P1 字典树是什么
顾名思义就像一个字典一样，可以查询某单词是否出现，也可以查找同一前缀的单词的个数等等操作。
P2 字典树的实现
字典树是用树来实现的（这不废话吗），如果从根节点走到一个已标记过的节点（后面我们会称它为单词节点）的一条路径就是一个单词。
我们定义一下变量（或数组）的表示含义：
- \(tot\): 表示当前一共有多少个节点。
- \(nex[p][c]\): 表示 \(p\) 节点的走 \(c\) 这条路径的下一个节点。
- \(exist[p]\): 表示 \(p\) 是否为单词节点。
- \(deta[p]\): 表示 \(p\) 节点的属性（权值），这个数组可有可无（通常为经过此节点的次数）。
很快我们就可以写出插入字符串，和查询字符串是否存在的代码，代码如下：
void insert(string s, int p = 0) {
for (int i = 0, c; i < s.size(); i++) {
c = ToId(s[i]); // ToId为字符转整数的函数
!nex[p][c] && (nex[p][c] = ++tot); // 若没有此节点，开辟新节点
p = nex[p][c] /*往下走*/, cnt[p]++; // 此处cnt为上述的deta，为经过此节点的次数
}
exist[p] = 1; // 将此节点标记为但此节点
}
bool query(string s, int p = 0) {
for (int i = 0, c; i < s.size(); i++) {
c = ToId(s[i]);
if (!nex[p][c]) {
return 0;
} // 没有路了没有此单词
p = nex[p][c]; // 往下走
}
return exist[p];
} // query的含义可以改变，此处是查询此字符串是否存在
很容易发现这个数据结构是一个用空间来换时间的数据结构，空间复杂度为：\(O(nmt)\)，\(n\) 表示单词的个数，\(m\) 表示单词的长度，\(t\) 表示字符的种类数。