Trie树
Trie树是一种可以高效的存储和查找字符串的数据结构。
先科普一下。
Trie树又叫前缀树
Trie树不光可以存储字符串，还可以存储数字甚至汉字！
* Trie树查找的时间复杂度近乎O(1)！
那我们的Trie树是如何存储或查找的呢？
其实Trie很简单。
Trie是一种非常简单的数据结构——yxc巨巨巨巨巨佬
那Trie树到底是如何用近乎O(1)这么NB的时间复杂度来去存储我们的字符串呢？
首先我们可以想像出一颗树，注意不一定是二叉树（二叉树就是每个父节点均有两个子节点。）
然后随便写一个单词（这里我写yxcnb），那我们把这个树进行如下操作：
具体请看视频。
在ACSABER的交流群中的文件里：
也可以打开美篇链接查看~
Trie树讲解~
不香看视频的同学这里我讲解一下。
每次我们插入一个字符串时先判断有没有对应字符串当前字符的节点。
如果有，我们走过去，否则我们新创建一个节点然后走过去。
这就是y总说的：
不管这个字符有没有路，它都走过去了，没有路会自己铺一条——yxc
那我们怎么查找呢？
我们可以每次判断与当前字符对应节点是否存在，如果不存在说明没有这个字符串，存在就继续走下去。
当然这一波下来还是很抽象，建议大家看看视频~
然后我们回来看看具体咋写。
首先我们定义一下需要用的数组~
int son[100010][26];/*所有的Trie题都会给定范围，默认范围是所有英文小写字母。*/
int idx;//当前用到的点。
char str[100010];//整个的字符串。
然后是插入操作。
void add(char *str)
{
int p = 0;//存储遍历到了什么店。
for(int i = 0; str[i]; i ++)//这里从前向后便利str字符串，最后\0会自动停止。
{
int u = str[i] - 'a';//算出当前值映射成数字后的数，减去偏移量a
if(!son[p][u]) son[p][u] = ++ idx;//没有路也要自己铺路。
p = son[p][u];//如果没有路已经铺好了路，走下去到下一个节点。
}
}
查找操作~
这里我们定义一个s数组查找。（通过字符串找到对应s数组中的值）
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 s[p];//最后返回对应s数组中的值
}
接下来一道题：Trie字符串统计
好我们先来读下题。
我们有两种操作分别为插入和查找，我们就能用Trie实现。
因为上面已经呈现过代码了所以直接上完整的AC代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 100010;
int n, son[N][26], cnt[N], idx;
char str[N];
void add(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];
}
int main()
{
cin >> n;
while(n --)
{
char op[2];
scanf("%s%s", op, str);
if(*op == 'I')
{
add(str);//插入操作就把字符串插进去
}
else cout<< query(str) << endl;//查找操作我们就返回查找
}
return 0;
}
