字典树的应用背景：
看以下几个题:
1、给出n个单词和m个询问，每次询问一个单词，回答这个单词是否在单词表中出现过
答:简单!map，短小精悍。
好。下一个
每次询问一个前缀，回答询问是多少个单词的前缀。2、给出n个单词和m个询问，
答:map，把每个单词拆开。
judge:n<=200000，TLE!
这就需要一种高级数据结构-Trie树(字典树)
截图的是--------------------------->Bilibili：董晓算法的内容
代码里面a是存储Trie树节点用的，a[p][u],里面u是表示英文字符，
字符
‘a’->0,
‘b’->1,
‘c’->2
p是代表第p个节点，a[p][u]值为k,那么k仅代表了编号
cnt[p]是代表了以p节点结尾这个单词出现次数！
这个trie树的知识点比较固定，似乎没有什么东西，死记硬背就好了
#include<iostream>
#include<string>
using namespace std;
#define MAX 100086
int N,a[MAX][27],idx,cnt[MAX];
string x,op;int query(string& ele){int p=0;for(int i=0;ele[i];++i){int u=ele[i]-'a';if(!a[p][u]){return 0;}p=a[p][u];}return cnt[p];
}
void insert(string& ele){int p=0;for(int i=0;ele[i]!='\0';++i){int u=ele[i]-'a';if(!a[p][u]){a[p][u]=++idx;}p=a[p][u];}cnt[p]++;
}
int main(){cin>>N;while(N--){cin>>op>>x;if(op=="Q"){cout<< query(x) <<endl;}else if(op=="I"){insert(x);}}return 0;
}
