字典树学习笔记
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…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
