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][u]初始为0，p代表当前接待你，u代表当前节点地某个子节点（u
的取值为0~25对应26个字母），即son[p][u]代表p节点下连接着下标为u的字母； -
插入操作：设置一个idx指向要操作的数组下标位置（作用同链表中的idx），每次插入一个字符串，循环处理每个字符。利用u=str[i]- 'a’将每个字符转化为整数操作，判断s[p][u]是否为0.若为0，不存在该字符，就插入该字符，即令son[p][u]=++idx,然后下移到字节点继续插入字符串的下一个字符；若不为0，就表示之前已经插入过该字符，直接下移。最后该字符串插入结束，设置一个数组cnt[]标记该字符串出现次数，cnt[p]表示以p结尾的字符串出现的次数；
-
查询操作：类似插入操作进行判断，若出现某一次son[p][u]为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~25if(!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树实现对字符串的统计应用。
)
