字典树 目录
原理
字典树又称前缀树，当我们要存储多个字符串时，若每段字符串单独存储，则查找以及空间效率都很低。
有一些字符串是另一些的前缀，或者两个字符串的前缀有重合，利用这一性质，我们建一个字典树，又叫前缀树，前缀相同的字符串前缀相同部分都只会被存储一次
例子
有字符串 a,ab ,acd,bc;
- 对于每个插入的字符串，首先从根节点出发，查找是否有匹配的子节点 如插入 "ab"时，首先在 root节点查找是否有 值为’a’的子节点，若没有，则直接插入。
- 再对该节点进行如第一步操作，继续查找是否有下一字符的节点。
- 若到达字符串尾部，则结束，标记该点。
结论
1.从根节点到任意被标记的节点，都是一个字符串。
2.有相同前缀的两个字符串，它们在树中一部分重复。
具体实现
虽然是树，但是一般不用指针实现，因为指针操作太繁琐
这里用的是数组实现，而每个节点存的就是它不是子节点的指针，而是下标 。
下面是节点结构：
struct tree{
int vis[26];//存子节点下标
int end;//判断是否是字符串
}ac[10000005];
- vis数组存储子节点下标，这个字典树处理的是英语字母上的字符串，字符集有26个元素，因此最多有26个子节点。
- end用来判断从根节点到该节点是否构成一个字符串。
构造：
int cnt;//trie树中结点个数
void build(int n){
int i,j,k,l,now;
for(i=0;i<n;i++){
scanf("%s",s);
l=strlen(s),now=0;//默认根节点下标为0
for(j=0;j<l;j++){
if(ac[now].vis[s[j]-'a']==0)//不存在
ac[now].vis[s[j]-'a']=++cnt;//插入结点
now=ac[now].vis[s[j]-'a'];//更新当前结点
}
ac[now].end+=1;//数目加一
}
}
- cnt存储的是结点个数
- vis子节点不存在默认初始化为0
- now存储当前结点
到了这里 一个trie树就建成了，至于具体应用？等我的ac自动机吧。