今天上午省选字符串......只会KMP、连hash都不会的我被大佬虐惨了......于是我要发奋图强学习字符串，学习字符串当然就要从Trie树这种可爱的数据结构开始啦！！！
一、什么是Trie树？？？
字典树，顾名思义，用来保存一些字符串。
二、Trie树的优势/用途？？？
那么就有人会问了：保存一些字符串，为什么不直接用数组？？？答案是显然的，你会收获MLE的好结果，于是我们考虑节省空间来保存他们的数据结构，于是Trie树就应运而生了！！！
三、核心思想？？？保存方法？？？
考虑存储两个单词ABA和ABC，我们可以利用他们有着共同前缀“AB”（因此Trie又被称为“前缀树”），于是我们可以建立一棵形如这样的Trie树：
A
|
B
|
————
| |
A C
我们发现，我们用了四个字符的空间，就存了六个字符，再加上动态开点，使得Trie的空间复杂度十分优秀。
四、Trie常用操作
插入/查询 是Trie的最基本操作：
插入代码如下（有详细注释，查询与之相似）
void insert(char *s)
{
int u=,len=strlen(s+);
//len为字符串长，u指向当前节点，最开始是根节点，指向0
for(int i=;i<=len;i++)
{
int c=idx(s[i]);//查询s[i]对应的数字
if(!ch[u][c])ch[u][c]=++cnt;//如果没有这个点，开一个新节点
u=ch[u][c];//顺着走一位
}
}
Trie插入
五、例题：
解析：
Trie树裸题，将所有学生的名字放进Trie树中。对于询问，如果一个人的名字中有的点为空，那么就是错的，如果是第一次查询，那么就是对的，否则就是重复了。
参考代码如下：
// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 500050
using namespace std;
struct Trie
{
int val[N],ch[N][],cnt;
int idx(char c){return c-'a';}
void insert(char *s)
{
int u=,len=strlen(s+);
for(int i=;i<=len;i++)
{
int c=idx(s[i]);
if(!ch[u][c])ch[u][c]=++cnt;
u=ch[u][c];
}
}
int search(char *s)
{
int u=,len=strlen(s+);
for(int i=;i<=len;i++)
{
int c=idx(s[i]);
if(!ch[u][c])return ;
u=ch[u][c];
}
if(!val[u]){val[u]=;return ;}
return ;
}
}trie;
int n,m;
char s[];
int main()
{
ios::sync_with_stdio();
cin>>n;
for(int i=;i<=n;i++)
{
cin>>(s+);
trie.insert(s);
}
cin>>m;
for(int i=;i<=m;i++)
{
cin>>(s+);
int res=trie.search(s);
if(res==)cout<<"WRONG"<<endl;
else if(res==)cout<<"OK"<<endl;
else cout<<"REPEAT"<<endl;
}
return ;
}
洛谷P2580