看注释

题目描述

include [HTML_REMOVED]

using namespace std;
const int N =1e6 + 10 ;
int son[N][26] , idx ;
int cnt[N];

void insert(string &b){

int p = 0 ; 
for(int i = 0 ; i< b.size() ; i++){
    int u = b[i] - 'a' ;
    if(son[p][u] == 0 ) son[p][u] =  ++ idx ; //son[p][u]!=0 means:there is a line between p and u ; 
                                            //son[p][u] == next p ;
    p = son[p][u];
}
cnt[p]++;             //p很有意思，如果两次p相同 其实就是代表同一个字符串
                      //也就是说不是相同字符串的p 也不会一样(因为son[p][u]会等于0，导致p = idx ++
                      // 而idx也是从来不会重复的 ！！！！！！

}

int query(string &b){
int p = 0 ;
for(int i = 0 ; i < b.size() ; i++){
int u = b[i] - ‘a’ ;
if(son[p][u] == 0 ) return 0 ; //找不到就return 0
p = son[p][u];
}
return cnt[p] ; //找到独一无二的p
}

int main(){
int n ; cin >> n ;
string a , b ;
while(n–){
cin >> a >> b ;
if(a==”I”)
insert(b);
else cout<< query(b) << endl;;
}
return 0 ;
}