当前位置：首页 > ops >正文

【AcWing 835题解】滑动窗口

ops 2025/7/27 12:00:11

AcWing 835. Trie字符串统计
【题目描述】
在这里插入图片描述
在查看解析之前，先给自己一点时间思考哦！
天津之眼
【题解】
可以使用Trie 树来解决这个问题，Trie树可以高效地支持字符串的插入和查询操作。

Trie树的基本概念：
Trie树是一种树形结构，用来存储字符串，其中每个节点表示一个字符。
每条从根节点到叶子节点的路径表示一个字符串。
每个节点的cnt数组用于记录该节点对应的字符串出现的次数。

插入操作：遍历字符串的每个字符，通过Trie树构建路径。如果路径不存在，就创建新的节点。最终在路径的末尾节点上增加出现次数。
查询操作：根据字符串的每个字符，沿着树路径向下查找。如果路径存在，则返回末尾节点的cnt值；如果路径不存在，说明该字符串没有插入过，返回0。
【参考代码】

#include <iostream>using namespace std;const int N = 100010;  // 最大节点数// son[i][j] 表示节点 i 的第 j 个子节点
int son[N][26], cnt[N], idx;  // son 数组、节点计数、当前索引
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 的数字，表示字母 a-zif (!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';  // 将字符转换为 0-25 的数字if (!son[p][u]) return 0;  // 如果找不到当前字符的子节点，返回 0p = 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;
}