字典树（Trie树）详解&例题[模板]字典树
字典树（Trie树）详解
理论模块：
trie 树
字典树是一种用于实现字符串快速检索的多叉树结构
trie 的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符
就沿着当前节点的
下图即为一个简易版字典树，存储了单词：abc、bac、abd
实现
(1) 初始化
一颗空 trie 仅包含一个根节点，该字符的指针均指向空
(2) 插入
当需要插入一个字符串
-
1.若
P 的c 字符指针指向一个已经存在的节点Q ,则令P=Q -
2.若
P 的c 字符指针指向空，则新建一个节点Q 令P 的c 字符指针指向Q ,然后令P=Q -
当
S 中的字符扫描完毕，在当前节点P 上标记它是一个字符串的末尾
(3) 检索
当需要检索一个字符串
-
(1) 若
P 的c 字符指针指向空，则说明S 没有被插入到Trie 树中，结束检索 -
(2) 若
P 的c 字符指针指向一个已经存在的节点Q ,则令P=Q 当
S 中的字符扫描完毕若在当前节点
P 被标记为一个 字符串的末尾，则说明 S 在 Trie 树中存在，否则说明 S 没有被插入过
#include<bits/stdc++.h>
using namespace std;
int trie[ ][ ],tot=1;
char str[ ];
bool end[ ];
void put()
{
//1
int len;
//2
int p=1;
//3
for(int i=1;i<=len;i++)
{
int ch=str[i]-'a';
trie[p][ch]
//(1)指向空
trie[p][ch]=++tot;
//(2)指向已存在
p=trie[p][ch];
}
//4
end[p]=true;
return;
}
bool find()
{
//1
int len;
//2
int p=1;
//3
for(int i=1;i<=len;i++)
{
int ch=str[i]-'a';
trie[p][ch]
//(1)指向空
return false;
//(2)指向已存在
p=trie[p][ch];
}
//4
return end[p];
}
int main(){
return 0;
}例题：luoguP8306[模板]字典树
分析：
给定
n 个模式串 1,2,…,s_1 ,s_2 ,…,s_n 和 q 次询问，每次询问给定一个文本串t_i ，请回答 1∼s_1 ∼s_n 中有多少个字符串s_j 满足t_i 是s_j 的前缀。
那么很明显，这道题主要考的就是我们对于字典树的运用。
除了上文所述的存储方法，还可以运用与其他树形结构相类似的结构体存储：
struct NODE{
int cnt=0;
int son[65];
}node[MAXN];不过字符还需要转换成一个数字，这里我们就需要用到一个类似于map映射的东西：
int getnumber(char ch)
{
if(ch>='A'&&ch<='Z')
return ch-'A';
if(ch>='a'&&ch<='z')
return ch-'a'+26;
return ch-'0'+52;
}//约等于map映射 插入操作：
void insert(string s)//插入操作，s表示需要插入的字符串
{
now=start;
for(int i=0;i<s.size();i++)
{
num=getnumber(s[i]);
if(node[now].son[num]==0)
node[now].son[num]=++cnt;
node[now].cnt++;
now=node[now].son[num];
}
node[now].cnt++;
return;
}查询操作：
void find(string s)
{
now=start;
for(int i=0;i<s.size();i++)
{
num=getnumber(s[i]);
if(node[now].son[num]==0)
{
printf("0\n");
return;
}
now=node[now].son[num];
}
printf("%d\n",node[now].cnt);
return;
}整个代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e6+5;
int num,now,start,cnt;
int T,n,q;
string s;
int getnumber(char ch)
{
if(ch>='A'&&ch<='Z')
return ch-'A';
if(ch>='a'&&ch<='z')
return ch-'a'+26;
return ch-'0'+52;
}//约等于map映射
struct NODE{
int cnt=0;
int son[65];
}node[MAXN];
void insert(string s)//插入操作，s表示需要插入的字符串
{
now=start;
for(int i=0;i<s.size();i++)
{
num=getnumber(s[i]);
if(node[now].son[num]==0)
node[now].son[num]=++cnt;
node[now].cnt++;
now=node[now].son[num];
}
node[now].cnt++;
return;
}
void find(string s)
{
now=start;
for(int i=0;i<s.size();i++)
{
num=getnumber(s[i]);
if(node[now].son[num]==0)
{
printf("0\n");
return;
}
now=node[now].son[num];
}
printf("%d\n",node[now].cnt);
return;
}
int main(){
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&q);
while(n--)
{
cin >> s;
insert(s);
}
while(q--)
{
cin >> s;
find(s);
}
start=++cnt;
}
return 0;
}