0%

字典树

字符串的处理方式极多,字典树便是其中一种

字典树基础

此篇重写,再无板子之谈

板子不理解的时候真能坑死人,还不如没有

常用二维数组存储,一般认为每个节点含有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]++即可。

基础数据结构重在插入,即树的构建,剩下的就是其多样的用法。