idx解释
每次新建一个节点,其编号就是用++idx来表示
p[r][t]也就是第r个节点有序号为t的子节点,值为子节点的编号
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int p[N][26];//存储每个节点的子节点
int idx,n;
int cnt[N];//以N结尾的字符串个数
void insert(char *str){
int r=0;
for(int i=0;str[i];i++){
int t=str[i]-'a';
if(!p[r][t]) p[r][t]=++idx;
r=p[r][t];
}
cnt[r]++;
}
int query(char *str){
int r=0;
for(int i=0;str[i];i++){
int t=str[i]-'a';
if(!p[r][t]) return 0;
r=p[r][t];
}
return cnt[r];
}
int main(){
cin>>n;
while(n--){
char task,str[N];
cin>>task>>str;
if(task=='I') insert(str);
else cout<<query(str)<<endl;
}
return 0;
}