$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

思路一：

1. son[p][u]表示爸爸是以 p 为结尾并且自己以 u 为结尾的单词
2. cnt[p]表示以 p 为结尾的单词的个数
3. idx 是全局变量，用于给建立的字母路径赋值

完整代码1

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;
char op,str[N];
int son[N][26],cnt[N],idx;

//插入单词
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        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;
        p=son[p][u];
    }

    return cnt[p];
}

int main()
{
    cin>>n;

    while(n--)
    {
        cin>>op>>str;

        if(op=='I') insert(str);

        if(op=='Q') cout<<query(str)<<endl;
    }

    return 0;
}

思路二：

利用 STL 的 map 用法直接统计单词

完整代码2

#include<bits/stdc++.h>

using namespace std;

int n;
string op,str;
map<string,int> cnt;

int main()
{
    cin>>n;

    while(n--)
    {
        cin>>op>>str;

        if(op=="I") cnt[str]++;

        if(op=="Q") cout<<cnt[str]<<endl;
    }

    return 0;
}