定义:高效得存储和查找字符串集合的数据结构
特点:
1、一层层向下查找,若不存在当前字符,插入一个对应的子结点
2、若存在以该字符为结尾的字符串,做标记
模板题835:
#include <iostream>
using namespace std;
const int N = 100010;
char str[N];
int son[N][26];
//存储子节点指针,例当前[idx][1]表a,它的值是idx+1,即指向[idx+1][2],而[idx+1][2]表b,即这部分是"ab",以此类推
int cnt[N];//以当前结点为结尾的字符串数量
int idx;
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];//p指向树中下一个字符继续比较
}
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 ;//若当前字符不存在,直接返回0
p = son[p][u];
}
return cnt[p];//返回字符串数量
}
int main(){
int n;
cin >> n;
while(n--){
char op[2];//小技巧,读入即使只有一个字符建议也用op[2],防止数据点输入中有空格回车等
cin >> op >> str;
if(op[0] == 'I') insert(str);
else cout << query(str) << '\n';
}
return 0;
}