Trie树(字典树)
什么是trie树
字典树，顾名思义，就是像字典一样的树，用来快速存储和查找字符串集合的数据结构。
就像下面这张图这样。
应用
Trie 树不止可以应用于字符串，只要某种信息表示可以以这种方式存储，都可以应用 Trie 树来存储，查找，或者维护某些信息。
检索字符串，如 AcWing 835.Trie字符串统计https://www.acwing.com/problem/content/837/
求最大异或对，AcWing 143.最大异或对 https://www.acwing.com/problem/content/145/
前缀统计， Acwing 142.前缀统计https://www.acwing.com/problem/content/144/
思路
存储：从root节点开始，看情况来创建字节点，如果这个节点已经有了，就走过去，如果还没有，就创建节点，然后走过去。单词结尾打上标记表明这是一个单词结束。
查找：和存储类似，但是如果查到一半查不到目标节点，或者到应该结束的地方没有结束，就说明查找失败。
代码模板
int son[N][26],cnt[N],idx;
//son[k][]存储第k个字符的子节点，cnt[k]存储以第k个字符为结束的单词的个数,idx表示当前用到哪个节点
char str[N];
void insert(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
int query(char * str){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}