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

数据结构--字典树(trie)

概念:

Trie 是一种能够快速插入和查询字符串的多叉树结构。、

节点的编号各不相同,根节点编号为0,其他节点用来标识路径,还可以标记单词的插入次数,边表示字符。

tire 维护字符串的集合,支持两种操作:

1. 向集合中插入一个字符串

2. 在集合中查询一个字符串

建字典树

儿子数组 son[p][26] : 存储从节点p沿着j这条边走到的子节点。边为26个小写字母(a~z)对应的映射值0~25,每个节点最多可以有26个分叉。

计数数组 cnt[p] : 存储以节点p结尾的单词的插入次数

节点编号 idx : 用来给节点编号

1. 空 trie 仅有一个根节点,编号为0

2. 从根开始插,枚举字符串的每个字符

     如果有儿子,则p指针走到儿子

     如果没有儿子,则 先创建儿子,p指针再走到儿子

3. 在单词结束点记录插入次数

模板:

int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串
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];
}

例题:(835. Trie字符串统计 - AcWing题库)

题目:

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

  1. I x 向集合中插入一个字符串 x;
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作,所有输入的字符串总长度不超过 105105,字符串仅包含小写英文字母。

输入格式

第一行包含整数 N,表示操作数。

接下来 N 行,每行包含一个操作指令,指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x,都要输出一个整数作为结果,表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗10^4

输入样例:

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例:

1
0
1

代码:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<queue>
#include<cstring>
#include<sstream>
#include<string.h>
#include<vector>const int N = 1e5 + 10;
using namespace std;
typedef pair<int ,int> PII;
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] ++;
}
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];scanf("%s%s",op,str);if(op[0] == 'I') insert(str);else printf("%d\n",query(str));}return 0;
}

相关文章:

数据结构--字典树(trie)

概念&#xff1a; Trie 是一种能够快速插入和查询字符串的多叉树结构。、 节点的编号各不相同&#xff0c;根节点编号为0&#xff0c;其他节点用来标识路径&#xff0c;还可以标记单词的插入次数&#xff0c;边表示字符。 tire 维护字符串的集合&#xff0c;支持两种操作&…...

iframe通过postMessage进行跨域通信以及在Angular中使用

写在前面 在前端开发过程中&#xff0c;会遇到一些需要使用iframe的场景&#xff0c;使用iframe关键的一个点是数据之间的传输&#xff0c;基于同源的要求十分苛刻&#xff0c;大家基本上是都是跨域的&#xff0c;如果跨域进行数据传输呢&#xff1f; 大家使用的比较多的就是p…...

rust学习-引用C库

link和extern #[link(name = "...")] 是一个用于链接外部库的属性宏。 可以在 Rust 代码中引入其他语言编写的动态链接库(.so、.dll 等文件),从而实现 Rust 和其他语言的互操作。 #[link(name = "...")] 属性宏用于在 Rust 模块中引入标准 C 库(如 m…...

WebAssembly 在云原生中的实践指南

1 WebAssembly 介绍 WebAssembly&#xff08;Wasm&#xff09;是一种通用字节码技术&#xff0c;它可以将其他编程语言&#xff08;如 Go、Rust、C/C 等&#xff09;的程序代码编译为可在浏览器环境直接执行的字节码程序。 WebAssembly 的初衷之一是解决 JavaScript 的性能问…...

Azure sqlserver 更改字符集

前言 我们的Azure SQL Server是在2018年建的&#xff0c;当时还不支持汉字的字符集。然后最近发现因为字符集的缘故&#xff0c;出了bug&#xff0c;要调整字符集。然后就照着sqlserver 排序规则&#xff08;字符集&#xff09;查看与修改 一通修改。 然后神奇的事情来了&…...

git push时,由于commit了大文件无法成功push的解决办法

2句命令解决&#xff01; 如图可以看见大文件的md5值&#xff0c;复制下来&#xff0c;以下命令会使用到 命令1&#xff1a; git rev-list --objects --all | grep b8d13387c0dfd7a8cec9ff0f6c8ded06eb21556f执行上面命令将得到&#xff0c;如下的输出&#xff0c;可以得知是…...

2023_Spark_实验一:Windows中基础环境安装

Ⅰ、WINDOWS中安装JDK1.8 一、下载安装包 链接&#xff1a;百度网盘 请输入提取码 所在文件夹&#xff1a;根目录或者大数据必备工具--》开发工具(前端后端)--》后端 下载文件名称&#xff1a;jdk-8u191-windows-x64.exe 二、安装JDK 1.现在转到下载的exe文件可用的文件夹&…...

如何在Windows / Mac / iPhone / Android / Online上将MP4转换为MP3

如果只想保留MP4视频的音频轨道&#xff0c;则可以将MP4转换为MP3格式。 MP3是几乎所有设备&#xff0c;播放器和编辑器都支持的数字音频格式。无论您将MP4视频转换为MP3音频以进行脱机播放或进一步编辑&#xff0c;都可以提取音轨并保存为MP3格式。这是在不损失质量的情况下将…...

【App端】uni-app使用百度地图api和echarts省市地图下钻

目录 前言方案一&#xff1a;echarts百度地图获取百度地图AK安装echarts和引入百度地图api完整使用代码 方案二&#xff1a;echarts地图和柱状图变形动画实现思路完整使用代码 方案三&#xff1a;中国地图和各省市地图下钻实现思路完整使用代码 前言 近期的app项目中想加一个功…...

深度学习(十)--- cv2.pointPolygonTest() 判断一点是否在指定区域内

今天发现了opencv一个好用的函数 cv2.pointPolygonTest() &#xff0c;它可以判断一个点是否在指定区域内。 1. cv2.pointPolygonTest() 函数解析 dist cv2.pointPolygonTest(contour,point,Boolean)contour: 多边形轮廓 point: 坐标点 Boolean:True或False &#xff0c;Tru…...

后端面试话术集锦第 八 篇:redis面试话术

这是后端面试集锦第八篇博文——redis面试话术❗❗❗ 1. 介绍一下redis Redis是一个非关系数据库,我们项目中主要用它来存储热点数据的,减轻数据库的压力,单线程纯内存操作,采用了非阻塞IO多路复用机制,就是单线程监听,我们项目中使用springdata-redis来操作redis。 我…...

LiteOS qemu realview-pbx-a9 环境搭建与运行

前言 最近打算移植搭建 一些常见的 RTOS 的 qemu 开发学习环境&#xff0c;当前 RT-Thread、FreeRTOS 已经成功运行 qemu&#xff0c;LiteOS 初步验证可以正常 运行 qemu realview-pbx-a9&#xff0c;这里做个记录 首先学习或者研究 RTOS&#xff0c;只是看内核源码&#xff0…...

Kubernetes技术--Kubernetes架构组件以及核心概念

1.Kubernetes集群架构组件 搭建一个Kubernetes环境集群,其架构如下所示: 内容详解: Master:控制节点,指派任务、决策 Node:工作节点,实际干活的。 Master组件内容:...

拿来即用修改密码功能

<template><div><!-- 重置密码 --><el-dialogtitle"修改密码"v-model"state.resetPwdDialogVisible":showClose"state.firstLogin ! 1"width"550px"close"onCancel":close-on-click-modal"false&…...

违背原则才能写好代码(一)

如果我说&#xff0c;要写好代码&#xff0c;必须违背这些原则&#xff0c;我想所有人都会骂&#xff1a;疯子、胡说八道、哗众取宠&#xff0c;找打&#xff01; 以前我也会骂那个疯子&#xff0c;但现在不会&#xff0c;而且我会肯定地、负责任地说&#xff1a;这是真的&…...

面试官眼中的理想候选人:如何成为他们的首选

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

ES6中的扩展运算符你真的会用吗?

本文不会具体介绍扩展运算符的基本用法。 只是分享在项目中踩坑的点。 你以为的扩展运算符只是复制的功能&#xff0c;其实会偷偷修改你的原数组 案例&#xff1a; 假如arr [...arr2] &#xff0c;修改arr的值会改变arr2的值吗? 解决方案&#xff1a; case1 使用 arr […...

利用逻辑回归判断病人肺部是否发生病变

大家好&#xff0c;我是带我去滑雪&#xff01; 判断肺部是否发生病变可以及早发现疾病、指导治疗和监测疾病进展&#xff0c;以及预防和促进肺部健康&#xff0c;定期进行肺部评估和检查对于保护肺健康、预防疾病和提高生活质量至关重要。本期将利用相关医学临床数据结合逻辑回…...

全民健康生活方式行动日,天猫健康联合三诺生物推出“15天持续测糖计划”

糖尿病是全球高发慢性病中患病人数增长最快的疾病&#xff0c;是导致心血管疾病、失明、肾衰竭以及截肢等重大疾病的主要病因之一。目前中国有近1.4亿成人糖尿病患者&#xff0c;科学的血糖监测和健康管理对于糖尿病患者来说至关重要。 在9月1日全民健康生活方式行动日前夕&am…...

设计模式行为型-状态模式

文章目录 简介状态模式基础定义状态接口或抽象类实现具体状态类 上下文类与状态转换上下文类的定义和作用状态转换及触发条件 状态模式的优势与适用性优点一&#xff1a;可维护的代码优点二&#xff1a;清晰的状态管理适用场景一&#xff1a;对象拥有多个状态适用场景二&#x…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

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

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

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

Modbus RTU与Modbus TCP详解指南

目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...