trietree3.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
const int MAX = 150001;
int path[MAX];
int endcnt[MAX];
int tree[MAX][26];
int cnt = 1;

void insert(string& word) {
    int cur = 1;
    for (int i = 0; i < word.length(); i++) {
        int temp = word[i] - 'a';
        if (tree[cur][temp] == 0)
            tree[cur][temp] = ++cnt;
        cur = tree[cur][temp];
        path[cur]++;
    }
    endcnt[cur]++;
}
int countstring(string& word) {
    int cur = 1;
    for (int i = 0; i < word.length(); i++) {
        int temp = word[i] - 'a';
        if (tree[cur][temp] == 0)
        {
            return 0;
        }
        cur = tree[cur][temp];
    }
    return endcnt[cur];
}
int countstringwith(string& word) {
    int cur = 1;
    for (int i = 0; i < word.length(); i++) {
        int temp = word[i] - 'a';
        if (tree[cur][temp] == 0)
        {
            return 0;
        }
        cur = tree[cur][temp];
    }
    return path[cur];
}
void deletestring(string& word) {
    if (countstring(word) > 0) {
        int cur = 1;
        path[cur]--;
        for (int i = 0; i < word.length(); i++) {
            int temp = word[i] - 'a';
            if (--path[tree[cur][temp]] == 0)
            {
                tree[cur][temp] = 0;
                return;
            }
            cur = tree[cur][temp];
        }
        endcnt[cur]--;
    }
}
void clear() {
    for (int i = 1; i <= cnt; i++) {
        memset(tree[i],0,sizeof(tree[i]));      //memset只能作用与数组  not vector
        path[i] = 0;
        endcnt[i] = 0;
    }
}

signed main()
{
    int m;
    cin >> m;
    int mod;
    while(cin >> mod)
    {
        string s;
        cin >> s;
        if(mod == 1) 
        insert(s);
        else if(mod == 2)
        deletestring(s);
        else if(mod == 3)
        {
            if(countstring(s) == 0)
            cout << "NO" << endl;
            else
            cout << "YES" << endl;
        }
        else
        {
            cout << countstringwith(s) << endl;
        }
    }
        clear();
}