$\large\color{blue}{C}$$\color{Blue}{++}\color{orange}{数据结构}\color{black}{————第五章}$
算法
$Trie$
不多说,就是一道模板题
C++ 代码
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int trie[100101][30],cnt[100110],tot=1;
void insert(string str){
int len=str.size(),p=1;
for(int i=0;i<len;i++){
int ch=str[i]-'a';
if(!trie[p][ch]) trie[p][ch]=++tot;
p=trie[p][ch];
}
cnt[p]++;
}
int search(string str){
int p=1;
for(int i=0;str[i];i++){
int ch=str[i]-'a';
if(trie[p][ch]==0) return 0;
p=trie[p][ch];
}
return cnt[p];
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
string op,str;
cin>>op>>str;
if(op[0]=='I') insert(str);
else printf("%d\n",search(str));
}
return 0;
}