trie字符串统计

 

#include<iostream>
using namespace std;
const int N=100010;
int idx,n;
int son[N][25];
int cnt[N];
char str[N];
char flag;

void insert(char s[]){
    int p=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u])
            son[p][u] = ++idx;
        p=son[p][u];
    }
    cnt[p]++;
}

int query(char s[]){
    int p=0;
    for(int i=0;s[i];i++){
        int u=s[i]-'a';
        if(!son[p][u])
            return 0;
        p=son[p][u];
    }
    return cnt[p];
}

int main(){
    scanf("%d",&n);
    while(n--){
        cin>>flag>>str;
        if(flag=='I') insert(str);
        else printf("%d\n",query(str));
    }
}

文章来源地址https://uudwc.com/A/woy0z