题目要求我们查询字符串出现次数，$Trie$ 树是将每个字符串存储为一种路径，在路径终点标记该字符串出现的次数，具体看下图

图中描述了 $8$ 个字符串 A, to, tea, ted, ten, i, in, inn 的存储结构。

我们用一个二维数组存储该树形结构，$son[N][26],$ 第一维表示树中的每个节点，第二维表示该节点的 $26$ 中选择（方向）$0$ ~ $25$ 分别表示下个字母是 $a$ ~ $z$，我们用 $son[x][y] = 0/1$ 表示当前节点是否存在，如果存在则继续向下走，不存在则 $x = idx$ ++ 创建一个新节点然后继续向下走，由于 $idx$ 一直增加，可以发现每个节点都是独一无二的 $idx$（那么每条路经的终点 $idx$ 也是独一无二的），我们前面讲的在路径终点标记该字符串出现的次数，此时开个新数组 $cnt$, $cnt[idx]$ 用来统计路径终点 $idx$ 被走到了多少次。

#include <iostream>

using namespace std;

const int N = 1000010;

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

void insert(char* str)//创建树形结构
{
    int p = 0;//从树的根节点开始
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';//映射到 0 ~ 25
        if (!son[p][u]) son[p][u] = ++idx;//不存在，创建一个新节点
        p = son[p][u];//从新节点p向下走
    }
    cnt[p]++;//路径终点次数++
}

int query(char* str)//查询字符串出现几次
{
    int p = 0;//从树的根节点开始
    for (int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';//映射到 0 ~ 25
        if (!son[p][u]) return 0;//如果我们之前没有创建过该节点，则不存在该路径
        p = son[p][u];//从新节点向下走
    }
    return cnt[p];//返回走到路径终点的次数
}

int main()
{
    int n;

    scanf("%d", &n);
    while (n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

STL

#include <iostream>
#include <map>
using namespace std;

const int N = 1000010;
char str[N];
map<string,int> mp;
int main()
{
    int n;

    scanf("%d", &n);
    while (n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I')
        {
            mp[str] ++;
        }
        else printf("%d\n", mp[str]);
    }

    return 0;
}