acwing算法基础之数据结构--trie算法
目录
- 1 基础知识
- 2 模板
- 3 工程化
1 基础知识
trie树算法,也叫作字典树算法。
用处:用来高效存储和查找字符串集合的数据结构。
(一)
定义变量。
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]++;return;
}
(三)
查询操作。
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];
}
2 模板
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]++;return;
}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];
}
3 工程化
class Trie {
public:Trie(int n) {this->n = n;son.resize(n, vector<int>(26, 0));cnt.resize(n, 0);idx = 0; //注意0表示根结点,也表示空结点。}Trie(int n, int m) {this->n = n;this->m = m;son.resize(n, vector<int>(m, 0));cnt.resize(n, 0);idx = 0; //注意0表示根结点,也表示空结点。}void insert(string str) {int p = 0;for (int i = 0; i < str.size(); ++i) {int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;return;}int query(string str) {int p = 0;for (int i = 0; i < str.size(); ++i) {int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];}
private:int n;int m;int idx;vector<vector<int>> son;vector<int> cnt;
};
相关文章:
acwing算法基础之数据结构--trie算法
目录 1 基础知识2 模板3 工程化 1 基础知识 trie树算法,也叫作字典树算法。 用处:用来高效存储和查找字符串集合的数据结构。 (一) 定义变量。 const int N 1e5 10; int son[N][26], cnt[N], idx; char str[N];(二…...
ES from+size>10000报错
参考博客 from size > 10000就会报错 Result window is too large, from size must be less than or equal to: [10000] but was [10001]. See the scroll api for a more efficient way to request large data sets. This limit can be set by changing the [index.max_…...
(04)Mycat实现分库
1、如何选择分库表 #客户表 rows:20万 CREATE TABLE customer(id INT AUTO_INCREMENT,NAME VARCHAR(200),PRIMARY KEY(id) );#订单表 rows:600万 CREATE TABLE orders(id INT AUTO_INCREMENT,order_type INT,customer_id INT,amount DECIMAL(10,2),PRIMARY KEY(id) ); #…...
DeepSORT多目标跟踪——算法流程与源码解析
一、目标检测与目标追踪 1. 目标检测 在目标检测任务中,主要目标是识别图像或视频帧中存在的物体的位置和类别信息。这意味着目标检测算法需要定位物体的边界框(Bounding Box)并确定每个边界框内的物体属于哪个类别(如人、汽车、…...
C++查漏补缺与新标准(C++20,C++17,C++11)02 C++快速回顾(二)
本内容参考C20高级编程 C风格的数组 //形如 int myArray[3]{2};一个比较新颖的获取C风格数组大小的函数std::size(),返回size_t类型(在中定义的无符号整数) #include <iostream> using namespace std;int main() {int myArray[5] {…...
红米K40功能介绍
红米K40是小米旗下的一款高性能智能手机。以下是红米K40的一些功能介绍及新增功能: 1.高性能处理器:红米K40搭载了骁龙870处理器,提供强大的性能和流畅的操作体验。 2.120Hz刷新率屏幕:红米K40采用了6.67英寸的AMOLED全面屏&…...
壹[1],Opencv常用结构
1,Point类:点表示 point表示二维结构的点,(x,y) cv::Point point; point.x 100; point.y 100; 2,Scalar类:颜色表示 cv::Scalar colorBlue(255,0,0);//蓝色 cv::Scalar colorGreen(0, 255, 0);//绿色 cv::Scalar colorRed(0, …...
Linux常用指令(一)——目录操作
Linux目录操作 1.1 目录切换 cd1.2 目录查看 ls1.3 创建目录 mkdir1.4 删除目录 rm1.5 复制目录 cp1.6 删除目录 rm1.7 搜索目录 find1.8 查看当前所在目录 pwd 更加完整的Linux常用指令 1.1 目录切换 cd # 切换到根目录 cd / # 切换到根目录的usr目录 cd /usr # 返回上一级目…...
前端基础之jQuery
一.什么是jQuery jQuery是一个轻量级的、兼容多浏览器的JavaScript库。jQuery使用户能够更方便地处理HTML Document、Events、实现动画效果、方便地进行Ajax交互,能够极大地简化JavaScript编程。它的宗旨就是:“Write less, do more.“ jQuery内部封装了…...
【基于HTML5的网页设计及应用】——实现个人简历表格和伪类选择器应用
🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:…...
思考(九十二):DBProxy实现多级存储和事务处理
DBProxy 数据处理的主控室 后端开发一块重要的内容就是如何处理数据。比如: 问题说明统一的访问界面如游戏服只需要 Load、Save、Begin、Commit、Rollback 接口多级存储来降低成本如热数据在 Redis ;冷数据在 MySQL ;长时间非活跃,则归档 OSS同个逻辑涉及多个数据更新要么…...
新手入门Python一定要看的八个超实用建议!
文章目录 前言一、项目文件事先做好归档二、永远不要手动修改源数据并且做好备份三、做好路径的正确配置四、代码必要的地方做好备注与说明五、加速你的Python循环代码六、可视化你的循环代码进度七、使用高效的异常捕获工具八、要多考虑代码健壮性关于Python技术储备一、Pytho…...
Centos 7.x上利用certbot申请Let‘s Encrypt的SSH证书(HTTPS证书)
目录 01-安装Certbot02-在网站的根目录依次新建文件夹.well-known和acme-challenge03-申请证书 要在CentOS 7.x上为域名申请Let’s Encrypt证书,你可以使用Certbot工具,它是一个自动化证书颁发工具,用于管理Let’s Encrypt证书。以下是在Cent…...
采用springboot、avue框架开发的:大型医院绩效考核系统成品源码
医院绩效考核系统全套源码(演示自主版权医院应用案例) 医院绩效考核系统,建立以医院发展目标为导向,以医务人员劳动价值、工作量为评价基础,统筹效率、质量、成本的绩效管理和绩效工资分配体系。系统支持RBRVS…...
时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解
时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解 目录 时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现FEEMD快速集合经验模态分解时间序列信号分解 算法新颖小众,…...
自学SLAM(6)相机与图像实践:OpenCV处理图像与图像拼接(点云)
前言 如果写过SLAM14讲第一次的作业,或者看过我之前的运行ORB_SLAM2教程应该都安装过OpenCV了,如果没有安装,没关系,可以看我之前的博客,里面有如何安装OpenCV。 链接: 运行ORB-SLAM2(含OpenCV的安装&…...
伊朗网络间谍组织针对中东金融和政府部门
导语 近日,以色列网络安全公司Check Point与Sygnia发现了一起针对中东金融、政府、军事和电信部门的网络间谍活动。这一活动由伊朗国家情报和安全部门(MOIS)支持的威胁行为者发起,被称为"Scarred Manticore"。该组织被认…...
基于51单片机土壤湿度检测及自动浇花系统仿真(带时间显示)
wx供重浩:创享日记 对话框发送:单片机浇花 获取完整源码源文件仿真源文件原理图源文件论文报告等 单片机土壤湿度检测及自动浇花系统仿真(带时间显示) 具体功能: (1)液晶第一行显示实际湿度&am…...
typeScript基础使用与进阶
typeScript基础使用与进阶 一、初始typeScript1.1 js的超集1.2 编译器编译为js代码1.3 完全兼容js1.4 静态类型检查器 二、ts的安装与编译2.1 ts的安装2.2 ts编译成js2.2.1 手动编译2.2.2 自动编译 三、ts基础使用3.1 类型声明3.1.1 基础类型3.1.2 数组3.1.3 对象3.1.4 any类型…...
云智慧联合北航提出智能运维(AIOps)大语言模型及评测基准
随着各行业数字化转型需求的不断提高,人工智能、云计算、大数据等新技术的应用已不仅仅是一个趋势。各行业企业和组织纷纷投入大量资源,以满足日益挑剔的市场需求,追求可持续性和竞争力,这也让运维行业迎来了前所未有的挑战和机遇…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
