AcWing 835. Trie字符串统计
原题链接
简单
#include<iostream>
using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx;//存小写字母所以每个节点最多向外连26条边,cnt存以当前节点结尾的单词有多少个,idx记录用到哪个节点(与单链表相同)
//下标是0的点既是根节点又是空节点
void insert(char str[]){
int p=0;//从整棵树的根节点0开始
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;//一维p是根节点,二维的值存放子节点,既下一个p的值
p=son[p][u];//p记录当前idx值为父节点并往下走指向下一个节点
}
cnt[p]++;//以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;
cin>>n;
while (n -- ){
char temp;
char str[N];
cin>>temp;
if(temp=='I') {
cin>>str;
insert(str);
}
if(temp=='Q') {
cin>>str;
cout<<query(str)<<endl;
}
}
return 0;
}
Hey boy!