题解 | #字典树的实现#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010;
int son[N][26], idx = 0;
int cnt[N], pass[N];

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

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

int prefixNumber(string s){
    int p = 0;
    for(int i = 0;i < s.size();i ++ ){
        int u = s[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return pass[p];
}

void delete_word(string s){
    if(!search_word(s)) return;
    int p = 0;
    for(int i = 0;i < s.size();i ++ ){
        int u = s[i] - 'a';
        p = son[p][u];
        pass[p] --;
    }
    cnt[p] --;
}

int main()
{
    int m;
    cin >> m;

    while(m --){
        int op;
        string s;
        
        cin >> op >> s;
        
        if(op == 1){
            insert_word(s);
        }else if(op == 2){
            delete_word(s);
        }else if(op == 3){
            search_word(s);
        }else if(op == 4){
            prefixNumber(s);
        }
    }

    return 0;
}

``