什么是Trie树
Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。 可以快速的在集合中查询某个字符串
Trie树的本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起
Trie的存储
Trie的存储形式就是构造成一个树形结构
比如我们以abcd，abce，abcd，abc，acbd，bcd这六个字符串为例
这里我们要把结尾的字符标记一下，圆圈表示根节点
每次我们向集合添加新的字符串时，我们一层一层的匹配，比如abcd，首先匹配a在 第一层是否出现过，没有出现过就创建这个节点，然后匹配b，看在下一个节点是否出 现过，没有就创建，出现的过的话继续往下匹配，在结尾处要标记一下，表示这个是字 符串的末尾。其他字符串一样，这样每一层最多也就26个字母。
Trie的查找
Trie可以高效的查询某个字符串在集合中是否出现过以及出现过多少次
比如我们现在向查找abcd，我们从根节点开始找，找到了a字母，然后根据a指向的 节点找到了b，最后找到d，d位置有标记了说明abcd在集合中出现过
如果我们查找不存在的字符串，比如abd，我们找到a，然后通过a指向的节点找到了 b，接着想通过b指向的节点找到d，结果发现没有，说明这个字符串不在集合中
案例
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 x；Q x询问一个字符串在集合中出现了多少次。共有 N 个操作，输入的字符串总长度不超过 1e5，字符串仅包含小写英文字母。
输入格式
第一行包含整数 NN，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为
I x或Q x中的一种。输出格式
对于每个询问指令
Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。每个结果占一行。
数据范围
1≤N≤2∗1e4
输入样例：
5 I abc Q abc Q ab I ab Q ab输出样例：
1 0 1
思路
这里我们用一个二维数组来存储Trie树，写算法题用数组模拟的话快一点
一个存层数，一个存字母的ASCLL值
先存储Trie树然后查询字符串，存储和查找的操作类似
代码实现
#include <iostream>
using namespace std;
const int N=1e5+10;
int s[N][26],cnt[N],idx;
char str[N];
//插入集合
void insert(char str[])
{int p=0;for(int i=0;str[i];i++){int u=str[i]-'0';if(!s[p][u]) s[p][u]=++idx;p=s[p][u];}cnt[p]++;
}
//查询操作
int Query(char str[])
{int p=0;for(int i=0;str[i];i++){int u=str[i]-'0';if(!s[p][u]) return 0;p=s[p][u];}return cnt[p];
}
int main()
{int m;cin>>m;while(m--){char op;cin>>op>>str;if(op=='I')insert(str);elsecout<<Query(str)<<endl;}return 0;
}
