题解 | 字典树的实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=150000+10;
int trieTree[MAXN][26];
int pass[MAXN];
int end_[MAXN];

int cnt;

void build(){
    cnt=1;
}

void insert(const string&word){
    int cur=1;
    pass[cur]++;
    for(char c:word){
        int path=c-'a';
        if(trieTree[cur][path]==0){
            trieTree[cur][path]=++cnt;
        }
        cur=trieTree[cur][path];
        pass[cur]++;
    }
    end_[cur]++;
}

int search(const string &word){
    int cur=1;
    for(char c:word){
        int path=c-'a';
        if(trieTree[cur][path]==0){
            return 0;
        }
        cur=trieTree[cur][path];
    }
    return end_[cur];
}

int prefixNumber(const string &prefix){
    int cur=1;
    for(char c:prefix){
        int path=c-'a';
        if(trieTree[cur][path]==0){
            return 0;
        }
        cur=trieTree[cur][path];
    }
    return pass[cur];
}

void Delete(const string&word){
    if(search(word)>0){
        int cur=1;
        pass[cur]--;
        for(char c:word){
            int path=c-'a';
            if(--pass[trieTree[cur][path]]==0){
                trieTree[cur][path]=0;
                return;
            }
            cur=trieTree[cur][path];
        }
        end_[cur]--;
    }
}

void clear(){
    for(int i=1;i<=cnt;i++){
        for(int j=0;j<26;j++){
            trieTree[i][j]=0;
        }
        pass[i]=0;
        end_[i]=0;
    }
}

int main(){
    int m,op;
    string line,word;
    while(getline(cin,line)){
        build();
        m=stoi(line);
        for(int i=0;i<m;i++){
            getline(cin,line);
            size_t k=line.find(' ');
            op=stoi(line.substr(0,k));
            word=line.substr(k+1);
            if(op==1){
                insert(word);   
            }else if(op==2){
                Delete(word);
            }else if(op==3){
                cout<<(search(word)!=0?"YES":"NO")<<endl;
            }else{
                cout<<prefixNumber(word)<<endl;
            }
        }
        clear();
    }
}