算法基础——Trie字符串统计
2024-08-31 17:59:57
题目:
维护一个字符串集合,支持两种操作:
“I x”向集合中插入一个字符串x;
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作,输入的字符串总长度不超过 10^5,字符串仅包含小写英文字母。
输入格式
第一行包含整数N,表示操作数。
接下来N行,每行包含一个操作指令,指令为”I x”或”Q x”中的一种。
输出格式
对于每个询问指令”Q x”,都要输出一个整数作为结果,表示x在集合中出现的次数。
每个结果占一行。
数据范围
1 ≤ N ≤ 2 ∗ 10^4
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
对于代码中一些变量和数组的分析和说明(看法)
int son[N][26];
son[N][26]这个数组表示的是,一个字符串通过26个字母组成,且长度不会超过N,所以开son数组开成[N][26]。
int cnt[N];
cnt[N]这个数组是用来记录在一个位置上被打上了多少次标记,该位置上打上的标记次数等于这个字符串出现的字数。
int idx;
idx 用来记录每一个字符的所在位置,方便后面询问(Query)时查找,表示现在最新的可用的下标是多少(和单、双链表中idx的作用类似)。
两个函数的意义,表达的思想,需要注意的是,我们是怎么把Trie树的理论转换成代码实现的
void Insert(char str[]){
int p = 0; /* 0表示根节点,0同时也表示节点为空(但在p = 0这里不是代表为空的意思),每次从根节点开始寻找 */
for(int i = 0; str[i]; i++){
int u = str[i] - 'a'; /* 将字母转换成数字,方便之后存入Trie树中 */
if(!son[p][u]) son[p][u] = ++ idx; /* 如果字符串中的某一个字符在Trie树中不存在,则创建该字符的节点 */
p = son[p][u]; /* 此时的p就是str中最后一个字符对应的trie树的位置idx。 */
}
cnt[p]++; /* 在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];
}
完整AC代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
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(){
int n;
scanf("%d", &n);
char op[2];
while (n--) {
char str[N];
scanf("%s%s", op, str);
if (op[0] == 'I') Insert(str);
else printf("%d\n", Query(str));
}
return 0;
}
最新文章
- nodejs pm2部署配置
- Linux设备树语法详解
- linux centos yum安装LAMP环境
- 又一种XML的解析方法
- Bluetooth Low Energy——蓝牙低功耗
- MVC模式介绍
- 人脸识别必读的N篇文章
- 随心所欲的DateTime显示格式
- Flexible 弹性盒子模型之CSS align-self 属性
- iOS网络模块优化(失败重发、缓存请求有网发送)
- 类Objects
- 探讨.NET Core中实现AES加密和解密以及.NET Core为我们提供了什么方便!
- GraphHttpClient概述
- softlab对接Jenkins工程
- solr 请求参数过长报错,Solr配置maxBooleanClauses属性不生效原因分析
- 《大道至简》第一章--编程的精意 读后感(JAVA伪代码)
- hive中数据存储格式对比:textfile,parquent,orc,thrift,avro,protubuf
- jquery扩展的两个方法与区别 $.extend $.fn.extend
- ParameterizedType获取java泛型参数类型
- 赵雅智:service_bindService生命周期
热门文章
- MySQL备份和恢复[2]-基于LVM的快照备份
- 不同系统执行相同shell脚本,出现Syntax error: ";("; unexpected错误解决
- hystrix线程池隔离的原理与验证
- springcloud中使用dubbo开发rpc服务及调用
- C语言之 判断语句基础与if语句反汇编
- CentOS 7 搭建 Ceph 集群(nautilus 版本)
- cookie与session的概念与区别
- 如何在 Debian 9 上搭建 LNMP 环境
- MYSQL中inner join、left join 和 right join的区别
- Python爬虫练习(requests模块)