简介:
Trie又称字典树,前缀树,是一种支持插入和查找字符串的多叉树,
每个节点对应一个字符,节点编号各不相同,根节点为0,其它节点编号用于标识路径,边表示字符
使用trie用于维护字符串集合,支持两种操作
1:void insert(char[])
向集合中插入一个字符串
2:int query(char[])
查询集合中莫格字符串出现的次数
数据储存:
子节点数组:
int son[p][u]
储存p号节点沿着u
这条边走到的子节点编号
第二维储存边,边为26个小写字母a~z的映射为0~25,即每个节点至多有26个分叉
比如:
son[0][2]=1
表示从0号节点(根节点)沿c边走到的节点是1号节点
son[1][0]=2
表示从1号节点沿着a边走到的节点是2号节点
son[2][19]=3
表示从2号节点沿着t边走到的节点是3号节点
计数数组:
int cnt[p]
储存以p号节点为结尾的字符串插入次数(每个节点是唯一的)
cnt[3]=1
表示以3号节点为结尾的字符串数量插入了1次(即”cat”插入1次)
节点编号:
int idx
全局变量用于给节点进行编号,每插入一个节点,就++,根节点和空节点都为NULL
插入流程:
1:空树有且仅有一个根节点,编号为0
2:从根节点开始遍历,枚举待插入串的每个字符同时转换成映射值
如果有子节点(有路径),指针p走到子节点
如果没有(无路径),先使用idx创建新的子节点,指针p再走到子节点
3;在字符串最末字符代表的节点处更新次数
模拟一下:
向空树中先后插入
cat
car
busy
cate
代码:
void insert(char str[]){
int p=0;//从根节点开始遍历
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
查找:
1:从根节点开始遍历,扫描字符串
2:如果无字符s[i],结束查找并直接返回0
3:如果有字符s[i],继续扫描查找,直到词尾匹配,则返回cnt[p]
代码:
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}
例题:acwing 835. Trie字符串统计 :https://www.acwing.com/problem/content/837/
例题完整代码: https://www.acwing.com/file_system/file/content/whole/index/content/7378828/