字典树

字典树

所谓字典树,其实就是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;
}