Trie样式

son[N][26]每一层最多26个字母
p表示的是某个父节点
son[p][u]表示的是p节点的下一层u这个字母是否存在
存在则非0，不存在则为idx下标
cnt[p]存的是以son[p][u]结尾下标为p的字符串数

判断是否存在字母 if(!son[p][u])

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx;

void insert(char *st) {
    int p = 0;//p为空的根节点
    for(int i = 0; st[i] != 0; ++ i) {
        int u = st[i] - 'a';//映射为0 - 25
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++;//打标记
}

int query(char *st) {
    int p = 0;
    for(int i = 0; st[i] != 0; ++ i) {
        int u = st[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
int main() {
    int n;
    cin >> n;

    while(n --) {
        char op, st[N];
        cin >> op >> st;

        if(op == 'I') insert(st);
        else cout << query(st) << endl;
    }
    return 0;
}