当前位置: 首页 > news >正文

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树算法&#xff0c;也叫作字典树算法。 用处&#xff1a;用来高效存储和查找字符串集合的数据结构。 &#xff08;一&#xff09; 定义变量。 const int N 1e5 10; int son[N][26], cnt[N], idx; char str[N];&#xff08;二…...

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. 目标检测 在目标检测任务中&#xff0c;主要目标是识别图像或视频帧中存在的物体的位置和类别信息。这意味着目标检测算法需要定位物体的边界框&#xff08;Bounding Box&#xff09;并确定每个边界框内的物体属于哪个类别&#xff08;如人、汽车、…...

C++查漏补缺与新标准(C++20,C++17,C++11)02 C++快速回顾(二)

本内容参考C20高级编程 C风格的数组 //形如 int myArray[3]{2};一个比较新颖的获取C风格数组大小的函数std::size()&#xff0c;返回size_t类型&#xff08;在中定义的无符号整数&#xff09; #include <iostream> using namespace std;int main() {int myArray[5] {…...

红米K40功能介绍

红米K40是小米旗下的一款高性能智能手机。以下是红米K40的一些功能介绍及新增功能&#xff1a; 1.高性能处理器&#xff1a;红米K40搭载了骁龙870处理器&#xff0c;提供强大的性能和流畅的操作体验。 2.120Hz刷新率屏幕&#xff1a;红米K40采用了6.67英寸的AMOLED全面屏&…...

壹[1],Opencv常用结构

1&#xff0c;Point类&#xff1a;点表示 point表示二维结构的点,(x,y) cv::Point point; point.x 100; point.y 100; 2&#xff0c;Scalar类&#xff1a;颜色表示 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交互&#xff0c;能够极大地简化JavaScript编程。它的宗旨就是&#xff1a;“Write less, do more.“ jQuery内部封装了…...

【基于HTML5的网页设计及应用】——实现个人简历表格和伪类选择器应用

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…...

思考(九十二):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证书&#xff0c;你可以使用Certbot工具&#xff0c;它是一个自动化证书颁发工具&#xff0c;用于管理Let’s Encrypt证书。以下是在Cent…...

采用springboot、avue框架开发的:大型医院绩效考核系统成品源码

医院绩效考核系统全套源码&#xff08;演示自主版权医院应用案例&#xff09; 医院绩效考核系统&#xff0c;建立以医院发展目标为导向&#xff0c;以医务人员劳动价值、工作量为评价基础&#xff0c;统筹效率、质量、成本的绩效管理和绩效工资分配体系。系统支持RBRVS&#xf…...

时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解

时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解 目录 时序分解 | Matlab实现FEEMD快速集合经验模态分解时间序列信号分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 Matlab实现FEEMD快速集合经验模态分解时间序列信号分解 算法新颖小众&#xff0c…...

自学SLAM(6)相机与图像实践:OpenCV处理图像与图像拼接(点云)

前言 如果写过SLAM14讲第一次的作业&#xff0c;或者看过我之前的运行ORB_SLAM2教程应该都安装过OpenCV了&#xff0c;如果没有安装&#xff0c;没关系&#xff0c;可以看我之前的博客&#xff0c;里面有如何安装OpenCV。 链接: 运行ORB-SLAM2&#xff08;含OpenCV的安装&…...

伊朗网络间谍组织针对中东金融和政府部门

导语 近日&#xff0c;以色列网络安全公司Check Point与Sygnia发现了一起针对中东金融、政府、军事和电信部门的网络间谍活动。这一活动由伊朗国家情报和安全部门&#xff08;MOIS&#xff09;支持的威胁行为者发起&#xff0c;被称为"Scarred Manticore"。该组织被认…...

基于51单片机土壤湿度检测及自动浇花系统仿真(带时间显示)

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;单片机浇花 获取完整源码源文件仿真源文件原理图源文件论文报告等 单片机土壤湿度检测及自动浇花系统仿真&#xff08;带时间显示&#xff09; 具体功能&#xff1a; &#xff08;1&#xff09;液晶第一行显示实际湿度&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)大语言模型及评测基准

随着各行业数字化转型需求的不断提高&#xff0c;人工智能、云计算、大数据等新技术的应用已不仅仅是一个趋势。各行业企业和组织纷纷投入大量资源&#xff0c;以满足日益挑剔的市场需求&#xff0c;追求可持续性和竞争力&#xff0c;这也让运维行业迎来了前所未有的挑战和机遇…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...