所谓字典树，其实就是n叉树。主要用于处理大量字符串，查找单词的操作。其原理是合并单词的公共前缀，再利用公共前缀大幅提供查找单词的效率。
举个栗子，比如有abc,abd,bc,c四个单词，构建树就如下图。
如上图，每个字典树都有一个0节点，接下来的节点建立按插入单词的顺序依次编号，相同前缀共用。
因此我们设**tree[root] [id]**存储一个节点的编号，root代表该节点父节点的编号，id则是该节点对应的字母。
（a-0，b-1，c-2……）
对于每个确实存在的单词，我们用**flag[tot]**数组来表示是否存在。例如上图中的flag[3]=true,代表存在abc这个单词。
下面贴上模板代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e6+5;
int tree[maxn][30],tot=0;
bool flag[maxn];
void add(string s)
{
int root=0,id,len=s.size();
for(int i=0;i<len;i++)
{
id=s[i]-'a';
if(!tree[root][id]) tree[root][id]=++tot;
root=tree[root][id];
}
flag[root]=true;
}
bool find(string s)
{
int root=0,id,len=s.size();
for(int i=0;i<len;i++)
{
id=s[i]-'a';
if(!tree[root][id]) return false;
root=tree[root][id];
}
if(flag[root]) return true;
else return false;
}
|