【题目来源】
AcWing：835. Trie字符串统计 - AcWing题库
【题目描述】
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 ；Q x询问一个字符串在集合中出现了多少次。
共有 \(N\) 个操作，所有输入的字符串总长度不超过 \(10^5\)，字符串仅包含小写英文字母。
【输入】
第一行包含整数 \(N\)，表示操作数。
接下来 \(N\) 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
【输出】
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 \(x\) 在集合中出现的次数。
每个结果占一行。
【输入样例】
5
I abc
Q abc
Q ab
I ab
Q ab
【输出样例】
1
0
1
【解题思路】
【算法标签】
《AcWing 835 Trie字符串统计》 #Trie#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010; // 定义Trie树的最大节点数// Trie树数据结构
int son[N][26]; // 存储每个节点的26个子节点（a-z）
int cnt[N]; // 记录以当前节点结尾的单词数量
int idx; // 当前可用的节点编号
char str[N]; // 临时存储输入的字符串// 向Trie树中插入字符串
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]; // 移动到子节点}cnt[p]++; // 标记单词结尾，增加计数
}// 查询字符串在Trie树中出现的次数
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]; // 返回以该节点结尾的单词数量
}int main()
{int n; // 操作次数scanf("%d", &n);while (n--) {char op[2]; // 操作类型scanf("%s%s", op, str);if (op[0] == 'I') insert(str); // 插入操作else printf("%d\n", query(str)); // 查询操作}return 0;
}
【运行结果】
5
I abc
Q abc
1
Q ab
0
I ab
Q ab
1