IT评测·应用市场-qidao123.com技术社区
标题:
Acwing Trie树
[打印本页]
作者:
用多少眼泪才能让你相信
时间:
2024-9-18 19:49
标题:
Acwing Trie树
Trie树（字典树）
告急用途：是用来高效存储和查找字符串集合的一种数据布局。查找时，可以高效的查找某个字符串是否在Trie树中出现过，并且可以查找出现了多少次
。
使用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比力，查询效率比哈希树高。
图示如下：
告急性子：
根节点不包含字符，除根节点外的每一个子节点都包含一个字符；
从根节点到某一个节点，路径上经过地字符毗连起来，为该节点对应地字符串；
每个节点地所有子节点包含的字符都不相同；
从第一字符开始有连续重复的字符只占用一个节点，好比上面的catch和cat中重复的单词cat只占用了一个节点。
Acwing 835 Trie字符串统计
维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入样例
：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
实现思绪：
设置一个二维数组son[p]
初始为0，p代表当前接待你，u代表当前节点地某个子节点（u
的取值为0~25对应26个字母），即son[p]
代表p节点下毗连着下标为u的字母；
插入操作：设置一个idx指向要操作的数组下标位置（作用同链表中的idx），每次插入一个字符串，循环处置惩罚每个字符。使用u=str
- 'a’将每个字符转化为整数操作，判定s[p]
是否为0.若为0，不存在该字符，就插入该字符，即令son[p]
=++idx,然后下移到字节点继承插入字符串的下一个字符；若不为0，就表示之前已经插入过该字符，直接下移。最后该字符串插入结束，设置一个数组cnt[]标记该字符串出现次数，cnt[p]表示以p结尾的字符串出现的次数；
查询操作：类似插入操作进行判定，若出现某一次son[p]
为0就此结束，意味着不存在该字符串，直到循环结束；若存在该字符串，返回计数数组cnt[p]。
具体代码：
#include <iostream>
using namespace std;
const int N=100010;
char str[N];
//son[][]存储树中每个节点的子节点
//cnt[]存储以每个节点结尾的单词数量
//idx表示当前用到了哪个下标
//0号点既是根节点，又是空节点
//插入一个字符串
int son[N][26],cnt[N],idx;
void insert(char str[]){
int p = 0;//树的指针，用于下移，初始指向根节点 根节点不存储字符
for(int i=0;str[i];i ++){
int u = str[i] - 'a';//u代表当前节点的某个子节点，映射为数字0~25
if(!son[p][u]) son[p][u] = ++ idx;//如果当前点不存在对应的字母，创建出来
//son[p][u]不为0代表p结点下连接着下标为u的字母
p=son[p][u];//指针下移
}
cnt[p] ++;//以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];//以p结尾的单词数量
}
int main(){
int n;
cin >> n;
while(n--){
char op;
cin >> op >> str;
if(op == 'I') insert(str);
else cout << query(str) << endl ;
}
return 0;
}
复制代码
以上就是Trie树实现对字符串的统计应用。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)
Powered by Discuz! X3.4
