字典树
字典树是一棵用来处理字符串的多叉树，其根节点为空字符，根节点到叶节点的路径组成了唯一的一个字符串。
字典树上的操作包括插入，搜索等。其一般用来解决字符串前缀问题。
字典树的构造
字典树的构造形式包含数组和结构体两种形式。
结构体形式一般如下：
struct Trie{
son;//子节点
isEnd;//用来表示是否为字符
target;//其他标志
}
C语言实例（仅包含26个小写字母的字典树）：
struct Node{
Node *son[26];
Node *fail;
int cnt;
Node(){
for(int i=0;i<26;i++){
son[i]=NULL;
}
fail=NULL;
cnt=0;
}
BuildTree(const char* str){
Node *now=this;
int len=strlen(str);
for(int i=0;i<len;i++){
int num=str[i]-'a';
if(now->son[num]==NULL){
now->son[num]=new Node();
}
now=now->son[num];
}
now->cnt=1;
}
} *p[MAX_L];
其中，子节点有几种不同的表示形式：
- 哈希函数
利用哈希函数将key映射到子元素，效率一般最高。 - 指针数组
按序号索引，适用于单个字符的字典树。 - Map
最方便，效率略低于哈希函数。
字典树上的操作：
字典树上的操作主要是查询，即查询目标串是否存在相匹配的模式串。
模板题
//POJ 3630
/*申请动态内存，会超时，所以要用静态内存代替*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAX_N=20;
int nextp=0;
struct Trie{
char num;
bool isPhone;
Trie(){
num=-1;
isPhone=false;
for(int i=0;i<10;i++)
sons[i]=NULL;
}
Trie(int num):num(num){
isPhone=false;
for(int i=0;i<10;i++)
sons[i]=NULL;
}
~Trie(){}
Trie * sons[10];
} head[1000000];
Trie * root;
char str[MAX_N];
int t,n;
bool flag;
bool add(const char* st){
int len=strlen(st);
int n_num=0;
Trie *now=root;
int v;
while(n_num<len){
v=st[n_num]-'0';
if(n_num==len-1&&now->sons[v]!=NULL)
return false;
if(now->sons[v]==NULL){
now->sons[v]=&head[nextp++];
}else{
if(now->sons[v]->isPhone){
return false;
}
}
now=now->sons[v];
if(n_num==len-1)
now->isPhone=true;
n_num++;
}
return true;
//for(int i=0;i)
}
int main(){
scanf("%d",&t);
while(t--){
root=&head[nextp++];
flag=true;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",&str);
if(!flag)
continue;
if(!add(str)){
flag=false;
}
}
if(flag){
printf("YES\n");
}
else
printf("NO\n");
}
return 0;
}
//POJ_2418
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<algorithm>
#include<string>
#include<fstream>
#include <iomanip>
using namespace std;
const int MAX_N=10500;
int n=0;
char tree[50];
struct Trie{
Trie* sons[127];
char ans[50];
bool isEnd;
int v;
Trie(){
isEnd=false;
for(int i=0;i<127;i++)
sons[i]=NULL;
v=0;
}
};
Trie* root;
void insert_Trie(const char* str){
int len=strlen(str);
Trie* now = root;
int num;
for(int i=0;i<len;++i){
num=str[i];
if(now->sons[num]==NULL)
{
now->sons[num]=new Trie();
}
now=now->sons[num];
}
now->isEnd=true;
now->v=now->v+1;
strcpy(now->ans,str);
}
void output(Trie* now){
if(now->isEnd){
printf("%s %.4f\n",now->ans,now->v*100.0/n);
}
for(int i=0;i<127;i++){
if(now->sons[i]!=NULL){
output(now->sons[i]);
}
}
}
int main(){
root=new Trie();
n=0;
while(gets(tree)!=NULL){
n++;
insert_Trie(tree);
}
output(root);
return 0;
}
