当前位置:网站首页>trie树模板
trie树模板
2022-08-05 10:28:00 【一条小小yu】
题目:Trie字符串统计
维护一个字符串集合,支持两种操作:
I x
向集合中插入一个字符串 xx;Q x
询问一个字符串在集合中出现了多少次。
共有 N个操作,输入的字符串总长度不超过 10^5,字符串仅包含小写英文字母。
输入格式
第一行包含整数 N,表示操作数。
接下来 N 行,每行包含一个操作指令,指令为 I x
或 Q x
中的一种。
输出格式
对于每个询问指令 Q x
,都要输出一个整数作为结果,表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗10^4 1≤N≤2∗10^4
输入样例:
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例:
1
0
1
#include<iostream>
using namespace std;
const int N=1e5+10;
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';
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;
}
边栏推荐
- High-quality DeFi application building guide to help developers enjoy DeFi Summer
- What is SPL?
- 秘乐短视频挖矿系统开发详情
- How can project cost control help project success?
- [Android] How to use RecycleView in Kotlin project
- 第六章:activiti流程分流判断之排它网关和并行网关
- 首次去中心化抢劫?近2亿美元损失:跨链桥Nomad 被攻击事件分析
- 阿里全新推出:微服务突击手册,把所有操作都写出来了PDF
- Opencv图像缩放和平移
- The host computer develops C# language: simulates the STC serial port assistant to receive the data sent by the microcontroller
猜你喜欢
Complete image segmentation efficiently based on MindSpore and realize Dice!
What are the standards for electrical engineering
three物体围绕一周呈球形排列
教你本地编译运行一个IDEA插件,在IDEA里聊天、下棋、斗地主!
电竞、便捷、高效、安全,盘点OriginOS功能的关键词
技术干货 | 基于 MindSpore 实现图像分割之豪斯多夫距离
登录功能和退出功能(瑞吉外卖)
MySQL transactions
PCB layout must know: teach you to correctly lay out the circuit board of the op amp
气象数据数据处理实例——matlab字符串切割匹配与R语言日期匹配(数据拼接)
随机推荐
Voice-based social software development - making the most of its value
DFINITY 基金会创始人谈熊市沉浮,DeFi 项目该何去何从
nyoj86 找球号(一) set容器和二分 两种解法
【温度预警程序de开发】事件驱动模型实例运用
[强网杯2022]WP-UM
012年通过修补_sss_提高扩散模型效率
This notebook of concurrent programming knowledge points strongly recommended by Ali will be a breakthrough for you to get an offer from a big factory
【MindSpore Easy-Diantong Robot-01】You may have seen many knowledge quiz robots, but this one is a bit different
[Translation] Chaos Net + SkyWalking: Better observability for chaos engineering
Offensive World-PWN-new_easypwn
[Strong Net Cup 2022] WP-UM
攻防世界-PWN-new_easypwn
一文道清什么是SPL
第六章:activiti流程分流判断之排它网关和并行网关
A small test of basic grammar, Go lang1.18 introductory refining tutorial, from Bai Ding to Hongru, basic grammar of go lang and the use of variables EP02
JS introduction to reverse the recycling business network of learning, simple encryption mobile phone number
NowCoderTOP35-40 - continuous update ing
如何修改管理工具client_encoding
字节一面:TCP 和 UDP 可以使用同一个端口吗?
MySQL transactions