C++

$\color{#cc33ff}{— > 算法基础课题解}$

$图解：$

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int son[N][26], cnt[N], idx;
//son存每个节点的子节点（儿子）
//由于只有26个字母，因此每个节点的子节点最多只有26个; cnt存以当前节点结尾的单词有多少个; idx存当前用到了那个下标
//下标是0的点，既是根节点，又是空节点
char str[N];


//Trie数

//插入操作
void insert (char str[]){
    int p = 0; // 从根节点开始
    for (int i = 0; str[i]; i ++){ //从前往后开始遍历
        int u = str[i] - 'a'; // 我们把a~z这26个字母映射为0~25
        if (!son[p][u]) son[p][u] = ++ idx; //如果当前点上不存在字母的话，我们就把它创建出来
        p = son[p][u]; //走到下一个点
    }

    cnt[p] ++; //以这个点结尾的单词多了一个
}

//查询操作
int query (char str[]){
    int p = 0; // 从根节点开始
    for (int i = 0; str[i]; i ++){
        int u = str[i] - 'a'; // 当前字母对应的子节点的编号
        if(!son[p][u]) return 0; //如果不存在，说明当前集合中是不存在这个单词的，直接返回0就可以了
        p = son[p][u]; // 否则的话就走过去
    }

    return cnt[p];//返回以p结尾的单词数量
}

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

    //n个操作
    while (n --){
        string op;
        cin >> op >> str;
        if (op == "I") insert (str);//执行插入操作
        else cout << query(str) << endl;//执行询问操作
    }
    return 0;
}