题目分析

利用树的结构实现字符串的插入与查找

这种思路太精彩了！

相关代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int son[N][26];
int idx=0;
int cnt[N];


void insert(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(son[p][u]==0) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;
}


int  query(string str){
    int p=0;
    for(int i=0;i<str.size();i++){
        int u=str[i]-'a';
        if(son[p][u]==0) return 0;
        p=son[p][u];
    }
    return cnt[p];
}


int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string op;
        string str;
        cin>>op>>str;
        if(op=="I")
            insert(str);
        else
            cout<<query(str)<<endl;

    }
    return 0;
}