Trie
luckydrawbox
·
·
个人记录
预处理
使用前，请根据需要更改字典树标准 standard。
如果应用范围为 26 个字母，你可以把 standard 设为 a。
如果应用范围为 01 串，你可以把 standard 设为 0。
操作
$\text{insert(s)}$：插入字符串 $s$。
$\text{remove(s)}$：删除字符串 $s$（如果存在的话）。
```cpp
struct Trie{
int tot;
char standard;
struct Tree{
int son[26];
int end;
}a[N];
Trie(){
tot=1;
standard='a';
}
int search(string str){
int len=str.size(),p=1;
for(int k=0;k<len;k++){
p=a[p].son[str[k]-standard];
if(!p)
return 0;
}
return a[p].end;
}
void insert(string str){
int len=str.size(),p=1;
for(int k=0;k<len;k++){
int ch=str[k]-standard;
if(!a[p].son[ch])
a[p].son[ch]=++tot;
p=a[p].son[ch];
}
a[p].end++;
}
void remove(string str){
int len=str.size(),p=1;
for(int k=0;k<len;k++){
int ch=str[k]-standard;
if(!a[p].son[ch])
return;
p=a[p].son[ch];
}
if(a[p].end)
a[p].end--;
}
};
```
单项操作时间复杂度 $O(len)$，其中 $len$ 是操作的字符串的大小，空间复杂度 $O(NC)$ ，其中 $N$ 是节点个数，$C$ 是字符集的大小。