首页 > 其他分享 >数据结构(六)串,Trie字符串统计---以题为例

数据结构(六)串,Trie字符串统计---以题为例

时间:2024-03-18 19:44:38浏览次数:23  
标签:char Trie ++ son --- int str 字符串 数据结构

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

  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
#include<iostream>
using namespace std;

const int N=1000010;
int son[N][26],idx,cnt[N];
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;
    cin>>n;
    while(n--){
        char op[2];
        cin>>op>>str;
        if(*op=='I')
            insert(str);
        else
            cout<<query(str)<<endl;
    }
    return 0;
}

 

标签:char,Trie,++,son,---,int,str,字符串,数据结构
From: https://www.cnblogs.com/Ghost-Knight/p/18081252

相关文章

  • L2-022 重排链表
    这道题真的烦,输出想半天。反正就是要区分奇偶,才能知道那个结点最后要打印出-1.我看网上遇到的都是测试点3的问题,不过我有问题的是测试点1,前三个出问题就是节点数奇偶的问题。#include<bits/stdc++.h>usingnamespacestd;map<int,pair<int,int>>mp;intmain(){ ints......
  • 华为OD机试真题-找数字-2024年OD统一考试(C卷)
    题目描述:小扇和小船今天又玩起来了数字游戏,小船给小扇一个正整数n(1<=n<=1e9),小扇需要找到一个比n大的数字m,使得m和n对应的二进制中1的个数要相同(如4对应二进制100,8对应二进制1000,1的个数都为1),现在求m的最小值。输入描述:输入:第一行输入一个正整数n(1<=n<=1e9)。输出......
  • 【操作系统】线程、程序、进程死锁的必要条件?如何避免死锁?死锁的预防,死锁的避免(银行
    目录线程、程序、进程死锁的必要条件?如何避免死锁?死锁的预防死锁的避免(银行家)死锁的检测进程-资源分配图死锁检测步骤死锁的解除线程、程序、进程进程是程序的一次执行过程,是系统运行程序的基本单位,因此进程是动态的。系统运行一个程序即是一个进程从创建,运行......
  • html--机器人
    <!DOCTYPEHTMLPUBLIC"-//W3C//DTDHTML4.0Transitional//EN"><HTML><HEAD><TITLE>NewDocument</TITLE><METANAME="Generator"CONTENT="EditPlus"><METANAME="Author"......
  • html--蝴蝶
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>蝴蝶飞舞</title><linkrel="stylesheet"href="https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.min.c......
  • JAVA--数据库(增删改)
    增(INSERT)#给指定字段添加数据insertinto表名(字段1,字段2...)values(值1,值2...);给全部字段添加数据insertinto表名values(值1,值2...);批量添加数据insertinto表名(字段1,字段2...)values(值1,值2...),(值1,值2...),(值1,值2...);   insertinto......
  • 数据可视化-ECharts Html项目实战(3)
    在之前的文章中,我们学习了如何创建堆积折线图,饼图以及较难的瀑布图并更改图标标题。想了解的朋友可以查看这篇文章。同时,希望我的文章能帮助到你,如果觉得我的文章写的不错,请留下你宝贵的点赞,谢谢。数据可视化-EChartsHtml项目实战(2)-CSDN博客文章浏览阅读1.2k次,点赞33次,收藏16......
  • 牛客网BC-30 时间转化(思路)
    题目如下我们可以简单分析一下第一步,我们需要输入秒数第二步,进行下简单的数学分析(如何转化为时分秒)第三步,输出时分秒---------------------------------------------------------------------------------------------------------------------------------    ......
  • Java详细安装教程--Java(jdk)安装附jdk安装包 不用登录oracle官网
    Java详细安装教程--Java(jdk)安装一、java历史简介1991年Sun公司的JamesGosling等人开始开发名称为Oak(橡树)的语言。希望用于控制嵌入在有线电视交换盒、PDA等的微处理器,1994年将Oak语言更名为Java1998年JDK1.2时,更名为Java2Platform分为标准版J2SE,企业版J2EE,微型版J2ME......
  • 第五篇:数字视频广告格式概述 - IAB视频广告标准《数字视频和有线电视广告格式指南》
    第五篇:第五篇:数字视频广告格式概述-IAB视频广告标准《数字视频和有线电视广告格式指南---我为什么要翻译介绍美国人工智能科技公司IAB系列技术标准(2)​​​​​​​翻译计划第一篇序言第二篇简介和目录第三篇概述-IAB受众和技术标准第四篇环境:移动设备、台式桌面设备、......