字典树（trie tree）
1.定义
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
2.性质
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同
3应用思路
假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树就是这样的。
1.存入
对于每一个单词从根节点开始向下延伸，将最后一个字母标记即图中的红色节点.
代码实现
void insert(char str[]){
int len=strlen(str),p=1;
for(int k=0;k<len;++k){
int ch=str[k]-'0';
if(trie[p][ch]==0) trie[p][ch]=++tot;
p=trie[p][ch];
}
book[p]=true;
}
2.查找
当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据.
代码实现
bool search(char str[]){
int len=strlen(str),p=1;
for(int k=0;k<n;++k){
p=trie[p][str[k]-'0'];
if(p==0) return false;
p=trie[p][ch];
}
return book[p];
}
代码不唯一,依题意进行修改.
4.例题
洛谷p2922
秘密信息 SecretMessage
【题目描述】
贝茜正在领导奶牛们逃跑。为了联络，奶牛们互相发送秘密信息。
信息是二进制的，共有 M(1≤M≤50000)条。反间谍能力很强的约翰
已经部分拦截了这些信息，知道了第 i 条二进制信息的前 bi(1≤bi≤10000)位。他同时知道，奶牛使用 N(1≤N≤50000)条密码。但是，他仅仅了解第 j 条密码的前 cj(1≤cj≤10000)位。
对于每条密码 j，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条密码有着相同的前缀。当然，这个前缀长度必须等于密码和那条信息长度的较小者。
在输入文件中，位的总数（即∑Bi+∑Ci）不会超过 500000.
【输入】SecretMessage.in
第 1 行输入 N 和 M，之后 N 行描述秘密信息，之后 M 行描述密码。
每行先输入一个整数表示信息或密码的长度，之后输入这个信息或密
码。所有数字之间都用空格隔开。
【输出】SecretMessage.out
共 M 行，输出每条密码的匹配信息数。
【样例输入】
4 5
3 0 1 0
1 1
3 1 0 0
3 1 1 0
1 0
1 1
2 0 1
5 0 1 0 0 1
2 1 1
【样例输出】
1
3
1
1
2
思路叙述
这道题在字典树上稍加修改即可
1.先记录下这个字符串走过的全部路径book[ ], 再记录下它的尾节点即最后一个字符en[ ]即可, 多个字符串通过同一节点时, 这个节点要增加记录.
2.在查找时, 当密码还未匹配完时且前面的都匹配. 有秘密信息匹配完了时ans加上以当前节点为末尾的字符串数即en[ ], 若密码不匹配且未匹配完了, 那么就直接返回ans.若密码匹配完了, 则令ans加上book[ ]在减去en[ ]. end在前已记录.
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
int n,m,k,a[10010];
struct ac{
int trie[maxn][2],tot,book[maxn],en[maxn];
void ins(int a[],int len){
int p=0;
for(int i=0;i<len;++i){
int ch=a[i];
if(!trie[p][ch]) trie[p][ch]=++tot;
p=trie[p][ch];
book[p]++;
}
en[p]++;
}
int found(int a[],int len){
int p=0,add=0,ch;
for(int i=0;i<len;++i){
ch=a[i];
if(trie[p][ch]){
p=trie[p][ch];
add+=en[p];
}
else{
return add;
}
}
add+=book[p]-en[p];
return add;
}
}ac;
int main(){
//freopen("SecretMessage.in","r",stdin);
//freopen("SecretMessage.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&k);
for(int j=0;j<k;++j){
scanf("%1d",&a[j]);
}
ac.ins(a,k);
}
for(int i=1;i<=m;++i){
scanf("%d",&k);
for(int j=0;j<k;++j){
scanf("%1d",&a[j]);
}
int ans=ac.found(a,k);
printf("%d
",ans);
}
return 0;
}
5.习题
yzoj 2116 玄武密码
yzoj 1773 Phone List