$\color{blue}{\texttt{C++}}$$\color{orange}{数据结构}\color{}{基础篇目录}$
$\ \ $
$$第五章 \ \ \ \ Trie$$
$\ \ \ $
$Trie$树,又名字典树,前缀树等,别称还不少
$Trie$树的特点就是能够实现字符串快速查找
废话不多说,接下来就来讲讲$Trie$树的一些基本操作
$Trie$树的基本操作
再次之前我们需要初始化一棵$trie$树,这很简单
int trie[100101][26]; //这里以26个小写字母为例
int tot=1;
insert插入
要在$trie$树中插入一个字符串,首先我们建一个指针,开始指向$trie$的根节点
扫描需要插入的字符串
沿着字符串的每个字符所在$Trie$树对应的节点往下走
如果该节点为空了,那么令该节点为当前$Trie$树的大小(++tot)
然后继续令指针指向当前节点
然后最后不要忘了,把字符串对应的最后一个节点标为$true$
void insert(string str){
int len=str.size(),p=1;
for(int i=0;i<len;i++){
int ch=str[i]-'a';
if(!trie[p][ch]) trie[p][ch]=++tot;
p=trie[p][ch];
}
end[p]=true;
}
search检索
在$Trie$树中查找一个字符串是否存在,跟插入差不多
也是用一个指针一直往下走,如果走不了了就直接返回$false$
如果能搜完,那么还要看是不是最后一个字符,如果是才能返回$true$,此处不细讲了
直接给大家上最喜欢的代码
int search(string str){
int len=str.size(),p=1,ans=0;
for(int i=0;i<len;i++){
int ch=str[i]-'a';
if(trie[p][ch]==0) return false;
p=trie[p][ch];
}
return end[p];
}
$Trie$树到这就讲完了
啥?不信?不信也得信
啥?可持久化$Trie$
至于可持久化$Trie$我会在之后的 $C++数据结构进阶篇第14章————可持久化数据结构$ 具体讲,这次就算了
其实是因为我还没学
下面是本贴相关题解:
AcWing 142. 前缀统计
AcWing 143. 最大异或对
AcWing 835. Trie字符串统计
之后可能还会有,敬请期待
最后的最后
练习网址戳这里