简述
字典树又称tire树，其为哈希树的变种，哈希树存的是键值字典树存的是字符。字典树用于统计，排序和保存大量字符，常用于搜索引擎，其本质是用字符串的公共前缀来优化查询。其查询过程就像我们在查新华字典，查询时间为O(len)。
树的样子
假设我们要存以下字符串："to","tea","ted","ten","a","i","in","inn"，那么树的样子是长这样的：
其中蓝色字符代表从根节点走到该字符拼出来的字符串存在，黑色表示只是字符串中间的字符。
树的储存
字典树是一颗多叉树，不是二叉树，所以一个节点可以有多个后继，若该字典树存的是小写字母，那么最多有26个后继。我们用结构体表示一个节点。
struct node{ int cnt; struct node *next[26]; node(){ cnt=0; memset(next,0,sizeof(next)); } };
cnt表示一个字典树到此有多少相同前缀的数目。
字符串的插入
插入的过程非常简单，无非是看前缀是否存在，若存在就共享，否则就创建新的节点。
例如我们要插入add，而ad已经存在。
•考虑第一个字符a，已经存在，继续往下走
•考虑第二个字符d，已经存在，继续往下走
•考虑第三个字符d，不存在，创建新的节点和边
void buildtrie(char *s){ node *p=root; node *tmp=NULL; int len=strlen(s); for(int i=0;i<len;i++){ if(p->next[s[i]-'a']==NULL){ tmp=new node; p->next[s[i]-'a']=tmp; } p=p->next[s[i]-'a']; p->cnt++; } }
其中对cnt的操作要会灵活变化，是每个字符都cnt++，还是最后一个字符++，要看题目的要求。
字符串的查找
查找的过程和插入的过程是类似的，从前缀开始一个一个查找，直到全部字符都查找成功或到某一节点找不到当前字符，就查找失败。返回这个字符串在字典树中作为前缀出现的次数，也就是cnt。
int findtrie(char *s){ node *p=root; int len=strlen(s); for(int i=0;i<len;i++){ if(p->next[s[i]-'a']==NULL){ return 0; } p=p->next[s[i]-'a']; } return p->cnt; }
内存的释放
有的时候题目数据量过大，查询完可能要放内存。
void del(node *root){ for(int i=0;i<26;i++){ if(root->next[i]) del(root->next[i]); } delete(root); }
内存的申请
字典树的内存有动态申请和静态申请两种，前者最慢，因为要一个一个空间开。后者最快，一次性把所有空间开好，但前提是题目给你结点上限了。
模板
动态申请：
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int t,n; char str[15]; struct node{ int cnt; struct node *next[26]; node(){ cnt=0; memset(next,0,sizeof(next)); } }; node *root; void buildtrie(char *s){ node *p=root; node *tmp=NULL; int len=strlen(s); for(int i=0;i<len;i++){ if(p->next[s[i]-'a']==NULL){ tmp=new node; p->next[s[i]-'a']=tmp; } p=p->next[s[i]-'a']; p->cnt++; } } int findtrie(char *s){ node *p=root; int len=strlen(s); for(int i=0;i<len;i++){ if(p->next[s[i]-'a']==NULL){ return 0; } p=p->next[s[i]-'a']; } return p->cnt; } void del(node *root){ for(int i=0;i<26;i++){ if(root->next[i]) del(root->next[i]); } delete(root); } int main() { root=new node; while(cin.getline(str,15)){ if(strlen(str)==0) break; buildtrie(str); } while(cin>>str){ cout<<findtrie(str)<<' '; } return 0; }
静态申请：
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=1e4+5; char str[maxn][15]; int cnt_node; struct node { int cnt; struct node *next[10]; void init() { cnt = 0; memset(next,0,sizeof(next)); } }Heap[maxn]; inline node* new_node(){//根据cnt_node一个一个提供结点 Heap[cnt_node].init(); return &Heap[cnt_node++]; } node *root = NULL; void buildtrie(char *s) { node *p = root; node *tmp = NULL; int i,l = strlen(s); for(i = 0; i < l; i++) { if(p->next[s[i]-'0'] == NULL) { tmp = new_node(); p->next[s[i]-'0'] = tmp; } p = p->next[s[i]-'0']; p->cnt++; } } bool findtrie(char *s) { node *p = root; int i,l = strlen(s); for(i = 0; i < l; i++){ p = p->next[s[i]-'0']; } if(p->cnt != 1) return true; return false; } int main() { int T; scanf("%d",&T); while(T--){ cnt_node = 0; root = new_node(); int n; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%s",str[i]); buildtrie(str[i]); } int flag = 1; for(int i = 1; i <= n; i++){ if(findtrie(str[i])){ flag = 0; break; } } if(flag) printf("YES "); else printf("NO "); } return 0; }