导读 ^ _ ^
Tire树是很关键的一种数据结构,你应该听过他的另外一个名字,即字典树,可以高效存储和查找字符串集合。
何为Tire树
一种高效存储和查找字符串集合的数据结构
结尾进行标记,统计出现次数
字符串统计
表示方式
son数组
- 第一维度用了表示节点,由idx控制
- 第二维度用来表示当前子节点枝条,有26个字母构成
cnt数组
- 用来统计当前节点出现的次数
关系映射
- 将字符 - ‘a’映射成数字
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;//注意0是根节点,又是空节点
char str[N];
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
}
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];
}
int main( ) {
int n;
scanf("%d", &n);
while(n--) {
char op[2];//过掉一个换行
scanf("%s%s",op,str);
if(op[0] == 'I')insert(str);
else printf("%d\n",query(str));
}
return 0;
}