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;
- }
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
