基本概念
Trie树又被称之为字典树，前缀树；
它是一种针对字符串进行维护的数据结构；
它也是一种可用来存储词典的数据结构；
核心思想
词典里的每个单词就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。
Trie树中存在一种被称之为目标节点的节点，即根节点到此节点的路径上，所有节点存储的字符连起来；
如图，橙色的节点为目标节点；
所以我们可以得到以下结果
a
abc
bac
bbc
ca
功能
字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。
1.字典，维护字符串集合；
2.建树，向字符串集合中插入字符串；
3.查询，查询字符串中是否存在某个字符；
4.统计，统计字符串在集合中出现的个数；
5.排序，将字符串集合按照字典序排序；
6.最长公共前缀，求集合内两个字符串的LCP；
因此，看到一大堆字符串出现时，一般往哈希和字典树想；
构建思路
对于每个用于字典的节点而言，广度最大为26。
因为每个节点的下一个字母，只可能是26个字母。
插入操作
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]; //使“p指针”指向下一个节点位置
}
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]; //返回字符串出现的次数
}
例题
以上构建思路以此题为中心；
https://www.acwing.com/problem/content/837/
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int son[N][26], cnt[N], idx;
char str[N];
void insert(string 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(string 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()
{
int t;
cin >> t;
while(t--)
{
string op;
string s;
cin >>op >> s;
if(op == "I")
{
insert(s);
}
else
{
int x = query(s);
cout << x << endl;
}
}
return 0;
}