字典树学习笔记
trie 树,即字典树,是一种可以实现 O ( S ) O(S) O(S) 的预处理( S S S 为所有字符串的长度和), O ( N ) O(N) O(N)( N N N 为查询的字符串的长度)的查询的数据结构。
举个栗子,对于字符串: abcd \texttt{abcd} abcd、 abd \texttt{abd} abd、 bcd \texttt{bcd} bcd、 efg \texttt{efg} efg,它的 trie 树如下:

那么,trie 树的建立、查询操作怎么代码实现呢?在此奉上蒟蒻的代码:
-
建立
int trie[maxn][30],cnt[maxn],tot; //trie[N][r]用来存储Trie树中的子节点(节点编号为N,它的字符儿子编号为r,比如trie[2][3]存储的就是节点编号为2,它的一个儿子为'd') //cnt[N]存储的是以当前结尾的字符串有多少个,tot存储当前共有几个节点 //下标是0的点,既是根节点,又是空节点 char str[N]; void insert(char *str) {int p=0;//根节点为0for(int i=0;str[i];i++){int u=str[i]-'a';//当前字母子节点if(!trie[p][u]) trie[p][u]=++tot;//如果当前子节点不存在就创造一个点来存储子节点p=trie[p][u];//让p走到子节点的位置cnt[p]++;//结尾是p的字符串个数增加} } -
查询
int query(char *str) {int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';//当前字母子节点的编号if(!trie[p][u]) return 0;//如果当前字符不存在那么直接返回0p=trie[p][u];//让p走到子节点的位置}return cnt[p];//最后返回以p结尾的字符串个数 }
练手板子题
代码如下:
#include <bits/stdc++.h>
using namespace std;const int maxn=2e6+5;
int t[maxn][65],cnt[maxn],tot;
char s[maxn];int getn(char x)
{if(x<='Z'&&x>='A') return x-'A';else if(x<='z'&&x>='a') return x-'a'+26;else return x-'0'+52;
}void insert(char s[])
{int p=0,len=strlen(s);//根节点为0for(int i=0;i<len;i++){int u=getn(s[i]);//当前字母子节点if(!t[p][u]) t[p][u]=++tot;//如果当前子节点不存在就创造一个点来存储子节点p=t[p][u];//让p走到子节点的位置cnt[p]++;//结尾是p的字符串个数增加}
}int ask(char s[])
{int p=0,len=strlen(s);for(int i=0;i<len;i++){int u=getn(s[i]);if(!t[p][u]) return 0;p=t[p][u];}return cnt[p];
}int main()
{int T;cin>>T;while(T--){for(int i=0;i<tot;i++)for(int j=0;j<65;j++) t[i][j]=0;for(int i=0;i<tot;i++) cnt[i]=0;tot=0;int n,q;cin>>n>>q;for(int i=1;i<=n;i++)cin>>s,insert(s);for(int i=1;i<=q;i++)cin>>s,cout<<ask(s)<<endl;}return 0;
}
相关文章:
字典树学习笔记
trie 树,即字典树,是一种可以实现 O ( S ) O(S) O(S) 的预处理( S S S 为所有字符串的长度和), O ( N ) O(N) O(N)( N N N 为查询的字符串的长度)的查询的数据结构。 举个栗子,对于…...
web各个指标理解
QPS : 单位时间得请求次数 TPS :单位时间得事务数 并发 : QPS *单位响应时间 pv :进入一个网站,又单击打开该网站的其他页面,每打开一个页面就 增加一个PV,甚至在同一页面每刷新一次也多一个PV 二八定律:百…...
Java后端开发(七)-- 在gitee上部署远程仓库,通过idea上传本地代码(用idea2022版本开发)
目录 1. 在Gitee上创建gitee远程仓库 2.在打开idea,再打开您要上传的idea代码,先创建 本地git仓库...
Go语言入门心法(十二): GORM映射框架
Go语言入门心法(一): 基础语法 Go语言入门心法(二): 结构体 Go语言入门心法(三): 接口 Go语言入门心法(四): 异常体系 Go语言入门心法(五): 函数 Go语言入门心法(六): HTTP面向客户端|服务端编程 Go语言入门心法(七): 并发与通道 Go语言入门心法(八): mysql驱动安装报错o…...
Ubuntu更新镜像源切换
概述 用ubuntu用apt命令,自动安装或更新包的时候,默认的镜像源服务器非常卡,很不方便。切换到国内的镜像源,下载更新非常快。为防止以后忘记,本文以国内服务器阿里巴巴的为例简单描述。 版本 Ubuntu23.10 找到更新…...
“一键合并剪辑,轻松添加片头——全新的视频编辑工具让你成为视频制作达人“
在日常生活中,我们时常会遇到需要制作视频的情况。但面对繁琐的视频剪辑和合并,你是否感到无从下手?今天,我们为你带来一款全新的视频编辑工具,让你轻松成为视频制作达人! 首先我们要进入好简单批量智剪主页…...
1.3 矩阵
一、向量与矩阵 下面是三个向量 u \boldsymbol u u、 v \boldsymbol v v、 w \boldsymbol w w: u [ 1 − 1 0 ] v [ 0 1 − 1 ] w [ 0 0 1 ] \boldsymbol u\begin{bmatrix}\,\,\,\,1\\-1\\\,\,\,\,0\end{bmatrix}\kern 10pt\boldsymbol v\begin{bmatrix}\,\,\,…...
阿里云-AnalyticDB【分析型数据库】总结介绍
一、背景 随着企业IT和互联网系统的发展,产生了越来越多的数据。数据量的积累带来了质的飞跃,使得数据应用从业务系统的一部分演变得愈发独立。物流、交通、新零售等越来越多的行业需要通过OLAP做到精细化运营,从而调控生产规则、运营效率、企…...
数二思维导图
高数上 第一章:函数、极限、连续 函数 函数的单调性、周期性、奇偶性复合函数 极限 求直接代入型的极限求∞∞型的极限用等价无穷小代换求00型的极限用洛必达法则求00型或∞∞型的极限求∞•0型的极限求幂指函数的极限函数的左右极限及需要求左右极限的情形极限的…...
ESXI6.5安装教程
设置从IPMI Virtual Disk 3000启动,出现如下界面: 默认选择第一项,回车安装 安装程序正在检测服务器硬件信息,如果不满足系统安装条件会跳出错误提示。 检测完成之后会出现下面界面 回车 按F11 这里列出了服务器硬盘信息&#…...
2023-9-25 美团售后服务系统后端一面【2024秋招】
1 实习 1.1 讲讲你做的一个需求,为什么这么做之类的 答: 1.2 什么是接线 1.3 什么的初始接线,和权威接线 答:初始接线是现状,权威是规划中的 1.4 为什么要做比较呢? 答:运维人员需要查看…...
YOLOv5改进实战 | GSConv + SlimNeck双剑合璧,进一步提升YOLO!
前言 轻量化网络设计是一种针对移动设备等资源受限环境的深度学习模型设计方法。下面是一些常见的轻量化网络设计方法: 网络剪枝:移除神经网络中冗余的连接和参数,以达到模型压缩和加速的目的。分组卷积:将卷积操作分解为若干个较小的卷积操作,并将它们分别作用于输入的不…...
Redis之zset在异步队列上的应用
当遇到并发的客户端请求时,为了缓解服务端的处理压力,当请求对响应的处理的实时性要求不高时,可以实现一个异步的请求消息队列。 一种实现策略是使用redis的zset,将消息的到期处理时间作为score,然后用多个线程去轮训…...
day4:Node.js 核心库
day4:Node.js 核心库 文章目录 day4:Node.js 核心库常用工具模块util 模块Moment 模块Lodash 模块web模块文件模块path 模块常用工具模块 Node.js有许多常用的工具,以下是一些常见的: util: 是一个Node.js 核心模块,提供常用函数的集合,用于弥补核心 JavaScript 的功能…...
PHP非对称与对称双向加密解密的方式
目录 RSA非对称加密解密: 什么是RSA非对称加密解密解析: 解析: 为什么使用: 有什么优点: DEMO: AES、DES、3DES等对称加密解密: 解析: 为什么使用: 有什么优点: DEMO: RSA非对称加密解密: 什么是RSA非对称加密解密解析: 解析: RSA非对称加密…...
C++之struct匿名结构体实例(二百四十四)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
npm publish发布到在线仓库时,提示:Scope not found
当npm publish发布时,控制台提示:Scope not found,具体错误信息如下: npm notice npm ERR! code E404 npm ERR! 404 Not Found - PUT https://registry.npmjs.org/xxx%2fxxx - Scope not found npm ERR! 404 npm ERR! 404 xxx/xx…...
AWS Lambda 操作 RDS 示例
实现目标 创建一个 Lambda 接收调用时传入的数据, 写入 RDS 数据库 Post 表存储文章信息. 表结构如下: idtitlecontentcreate_date1我是标题我是正文内容2023-10-21 15:20:00 AWS 资源准备 RDS 控制台创建 MySQL 实例, 不允许 Public access (后面 Lambda 需要通过 VPC 访问…...
【java爬虫】使用selenium获取某交易所公司半年报数据
引言 上市公司的财报数据一般都会进行公开,我们可以在某交易所的官方网站上查看这些数据,由于数据很多,如果只是手动收集的话可能会比较耗时耗力,我们可以采用爬虫的方法进行数据的获取。 本文就介绍采用selenium框架进行公司财…...
MATLAB - 不能使用PYTHON,缺少matplotlib模块的解决办法
matlab缺少python-matplotlib模块的解决办法 1. 前言、概述2. 解决办法3. 可能出现问题4. 结果 1. 前言、概述 起因是我用习惯的colormap函数getPyPlot_cMap不能用了:【这个函数要调用PYTHON】 报错的地方: ModuleNotFoundError: No module named ‘ma…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
反射获取方法和属性
Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
