题解 | #字典树的实现#

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>

using namespace std;

const int MAXN = 150001;
vector<vector<int>> tree(MAXN, vector<int>(26, 0)); // 二维数组
vector<int> endCount(MAXN, 0); // 结束标志
vector<int> pass(MAXN, 0); // 前缀计数
int cnt = 1;

void build() {
    cnt = 1;
}

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

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

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

void deleteWord(const string& word) {
    if (search(word) > 0) {
        int cur = 1;
        for (char ch : word) {
            int path = ch - 'a';
            if (--pass[tree[cur][path]] == 0) {
                tree[cur][path] = 0;
                return;
            }
            cur = tree[cur][path];
        }
        endCount[cur]--;
    }
}

void clear() {
    for (int i = 1; i <= cnt; i++) {
        fill(tree[i].begin(), tree[i].end(), 0);
        endCount[i] = 0;
        pass[i] = 0;
    }
    cnt = 1;
}

int main() {
    int m, op;
    string line, word;
    while (getline(cin, line)) {
        m = stoi(line);
        build();
        for (int i = 1; i <= m; i++) {
            getline(cin, line);
            stringstream ss(line);
            ss >> op >> word;
            if (op == 1) {
                insert(word);
            } else if (op == 2) {
                deleteWord(word);
            } else if (op == 3) {
                cout << (search(word) > 0 ? "YES" : "NO") << endl;
            } else if (op == 4) {
                cout << prefixNumber(word) << endl;
            }
        }
        clear();
    }
    return 0;
}