字符串的处理方式极多，字典树便是其中一种
字典树基础
此篇重写，再无板子之谈
板子不理解的时候真能坑死人,还不如没有
常用二维数组存储，一般认为每个节点含有26个子节点，分别表示字符a到z，编号1-26. 定义$trie[u][id]=k$中,u表字典树的节点编号，id表示该节点中编号为id的字符，u在全局中唯一，唯一标识每个节点。k即表示u的id子节点的编号。
插入字符串
1
2
3
4
5
6
7
8
9
10
11
12
| int tot=0;//tot表示节点总数/节点编号
void insert(string s){
int pos=0;
for(int i=0;i<s.size();i++){
int id=s[i]-'a';
if(tree[pos][id]==0){
tree[pos][id]=++tot;
}
pos=tree[pos][id];
}
tag[pos]=1;
}
|
查找字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int find(string s){
int pos=0;
for(int i=0;i<s.size();i++){
int id=s[i]-'a';
if(tree[pos][id]==0){
return -1;
}
pos=tree[pos][id];
}
if(tag[pos]==1){
return 1;
}
else{
return -1;
}
}
|
字典树的活用
求多项字符串的最大公共前缀长度之和
此时需要记录每个节点有几个字符串经过了这个节点，即节点需记录通过自己的字符串数量。
实现：每次插入过程中pos更新时同时cnt[pos]++即可。
基础数据结构重在插入，即树的构建，剩下的就是其多样的用法。