当前位置: 首页 > news >正文

Trie字符串统计

Trie字符串统计

维护一个字符串集合,支持两种操作:

  1. I x 向集合中插入一个字符串 x;
  2. Q x 询问一个字符串在集合中出现了多少次。
    共有 N个操作,所有输入的字符串总长度不超过 105,字符串仅包含小写英文字母。
    输入格式
    第一行包含整数 N,表示操作数。
    接下来 N行,每行包含一个操作指令,指令为 I x 或 Q x 中的一种。

输出格式
对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗104
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1

//用来快速存储、高效和查找字符串集合的    Trie树
#include<iostream>using namespace std;const int N=1e5+10;int son[N][26],cnt[N],idx;//son[N][26]每个节点最多有26个节点、cnt[N]以当前节点有多少个单词、idx存储当前用到的下标
//下标是0的点,既是根节点,又是空节点
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];}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);while(n--){char op[2];scanf("%s%s",op,str);if(op[0] == 'I') insert(str);//插入操作else printf("%d\n",query(str));//查询操作}return 0;
}

相关文章:

Trie字符串统计

Trie字符串统计 维护一个字符串集合&#xff0c;支持两种操作&#xff1a; I x 向集合中插入一个字符串 x&#xff1b;Q x 询问一个字符串在集合中出现了多少次。 共有 N个操作&#xff0c;所有输入的字符串总长度不超过 105&#xff0c;字符串仅包含小写英文字母。 输入格式…...

Kali Linux源

中科大 deb http://mirrors.ustc.edu.cn/kali kali-rolling main non-free contrib deb-src http://mirrors.ustc.edu.cn/kali kali-rolling main non-free contrib阿里云 deb http://mirrors.aliyun.com/kali kali-rolling main non-free contrib deb-src http://mirrors.…...

【RT摩拳擦掌】基于RT106L/S语音识别的百度云控制系统

【RT摩拳擦掌】基于RT106L/S语音识别的百度云控制系统 一 文档简介二 平台构建2.1 使用平台2.2 百度智能云2.2.1 物联网核心套件2.2.2 在线语音合成 2.3 playback语音数据准备与烧录2.4 开机语音准备与添加2.5 唤醒词识别词命令准备与添加 三 代码准备3.1 sln-local/2-iot 代码…...

国标GB28181视频汇聚平台EasyCVR设备展示数量和显示条数不符的原因排查与解决

国标GB28181/GA/T1400协议/安防综合管理系统EasyCVR视频汇聚平台能在复杂的网络环境中&#xff0c;将前端设备统一集中接入与汇聚管理。智慧安防/视频存储/视频监控/视频汇聚EasyCVR平台可以提供实时远程视频监控、视频录像、录像回放与存储、告警、语音对讲、云台控制、平台级…...

FastAPI教程I

本文参考FastAPI教程https://fastapi.tiangolo.com/zh/tutorial 第一步 import uvicorn from fastapi import FastAPIapp FastAPI()app.get("/") async def root():return {"message": "Hello World"}if __name__ __main__:uvicorn.run(&quo…...

如何在 HTML 中实现响应式设计以适应不同设备的屏幕尺寸?

要在HTML中实现响应式设计以适应不同设备的屏幕尺寸&#xff0c;可以使用CSS媒体查询和流动布局。 以下是实现响应式设计的一些关键步骤&#xff1a; 使用CSS媒体查询&#xff1a;CSS媒体查询允许根据屏幕尺寸和设备特性应用不同的CSS样式。通过在CSS中使用media规则&#xf…...

【基础篇】第1章 Elasticsearch 引言

1.1 Elasticsearch简介 1.1.1 基本概念 Elasticsearch&#xff0c;一个开源的分布式搜索引擎&#xff0c;以其强大的搜索能力和实时数据分析能力&#xff0c;在大数据时代脱颖而出。它基于Apache Lucene库构建&#xff0c;旨在提供高效、可扩展且易于使用的全文检索解决方案。…...

在区块链技术广泛应用的情况下,C 语言如何在区块链的底层开发中发挥更有效的作用,提高性能和安全性?

C语言在区块链底层开发中发挥着重要的作用&#xff0c;可以提高性能和安全性。具体可以从以下几个方面进行优化&#xff1a; 性能优化&#xff1a;C语言是一种高效的编程语言&#xff0c;可以直接访问内存和硬件资源。在区块链底层开发中&#xff0c;使用C语言可以更好地利用底…...

量化投资 日周月报 2024-06-28

文章 深度学习在量化交易中的应用:在BigQuant量化交易平台的文章中,探讨了深度学习在量化交易中,特别是在因子挖掘方面的应用。文章提到,随着传统线性模型的潜力逐渐枯竭,非线性模型逐渐成为量化交易的主要探索方向。深度学习因其对非线性关系的拟合能力,在量化交易中展现…...

基于 Paimon 的袋鼠云实时湖仓入湖实战剖析

在当今数据驱动的时代&#xff0c;企业对数据的实施性能力提出了前所未有的高要求。为了应对这一挑战&#xff0c;构建高效、灵活且可扩展的实时湖仓成为数字化转型的关键。本文将深入探讨袋鼠云数栈如何通过三大核心实践——ChunJun 融合 Flink CDC、MySQL 一键入湖至 Paimon …...

IPython相关了解

一、什么是 IPython&#xff1f; 1.1 简单理解 IPython IPython 是一种增强的 Python 交互式解释器&#xff0c;它可以让你更方便地编写、调试和运行 Python 代码。你可以把它想象成一个比普通 Python 解释器更聪明、功能更丰富的工具&#xff0c;非常适合用来进行数据探索、…...

华为面试题及答案——机器学习(二)

21. 如何评价分类模型的优劣? (1)模型性能指标 准确率(Accuracy): 定义:正确分类的样本数与总样本数之比。适用:当各类样本的数量相对均衡时。精确率(Precision): 定义:预测为正类的样本中实际为正类的比例。适用:当关注假阳性错误的成本较高时(例如垃圾邮件检测…...

PlatformIO开发环境

PlatformIO是一个开源的生态系统&#xff0c;用于构建物联网应用&#xff0c;它支持多种微控制器&#xff08;MCU&#xff09;和硬件开发板&#xff0c;并且与各种IDE集成良好&#xff0c;如VSCode, Atom等&#xff0c;使得跨平台的固件开发变得更加简单和高效。 ### 平台介绍…...

In install.packages(“devtools“, verbose = TRUE) :

错误于curl::curl_download("https://r-lib.github.io/gert/libgit2-1.1.0.x86_64_legacy-linux.tar.gz", : Timeout was reached: [] Connection timed out after 10004 milliseconds 停止执行 Using PKG_CFLAGS Using PKG_LIBS-lgit2 ----------------------------…...

计算机网络 访问控制列表以及NAT

一、理论知识 1. 单臂路由 单臂路由是一种在路由器上配置多个子接口的方法&#xff0c;每个子接口代表不同的 VLAN&#xff0c;用于在一个物理接口上支持多 VLAN 通信。此方法使得不同 VLAN 之间可以通过路由器进行通信。 2. NAT (网络地址转换) NAT 是一种在私有网络和公共…...

使用Oracle IMP导入数据

使用Oracle IMP导入数据 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01;今天我们来聊一聊如何使用Oracle的IMP工具来导入数据。 一、什么是Oracle IMP Oracle…...

C++ 100 之 容器插入和删除

vector插入和删除操作 insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele. push_back(ele); //尾部插入元素ele pop_back();//删除最后一个元素 erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素 erase(c…...

提升 Selenium 测试稳定性的秘诀:深入理解等待 API 的使用

目录 为什么需要等待Selenium 等待 API 简介隐式等待显式等待Fluent Wait等待策略的选择示例代码总结 正文 1. 为什么需要等待 在 Web 自动化测试中&#xff0c;等待是一个关键因素。网络应用通常是动态的&#xff0c;页面加载时间、元素的显示时间都可能不同步。直接操作这…...

Python-算法编程100例-滑动窗口(入门级)

题目1&#xff1a;最大连续1的个数&#xff08;简单&#xff09; 给定一个二进制数组 nums &#xff0c; 计算其中最大连续 1 的个数。 解答&#xff1a;前缀和双指针 # 给定一个二进制数组 nums &#xff0c; 计算其中最大连续 1 的个数。 from typing import Listclass So…...

ffmpeg使用mjpeg把yuvj420p编码为jpg图像

version #define LIBAVUTIL_VERSION_MAJOR 58 #define LIBAVUTIL_VERSION_MINOR 12 #define LIBAVUTIL_VERSION_MICRO 100 node 不使用AVOutputFormat code void CFfmpegOps::EncodeYUVJ420pToMJPEG(const char* infile, const char* width_str, const char* height_s…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...