trie算法

1、定义

高效的存储和查找字符串集合的数据结构

它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高

2、构建

我们可以使用数组来模拟实现Trie树。

我们设计一个二维数组 son[N] [26] 来模拟整个树的结构,而cnt[N] 来记录单词个数。

举个例子: son[1][1]=2 代表的是 1号节点 的一个值为b的节点 是 2号节点。而son[1][0]=0 则表示1号节点不存在 值为 a 的节点。

在这里插入图片描述

在这里插入图片描述

3、代码分析

1、定义

son[N][26]

下标是x的点

x这个节点的所有的儿子是去存储到son[x][26]里面

son[x][0]就是第一个节点 son[x][1]就是第二个节点

cont[x]表示以x为结尾的单词有多少个

int son[N][26], cnt[N], idx;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
2、插入操作
// 插入一个字符串
void insert(char *str)
{int p = 0;//从根节点开始,从前往后遍历for (int i = 0; str[i]; i ++ ){//将a-z 映射成  0 - 25int u = str[i] - 'a';//如果当前节点不存在 => p节点不存在u这个儿子//就创建出来if (!son[p][u]) son[p][u] = ++ idx;//将该值赋给pp = son[p][u];}//以该点为结尾的数字多了一个cnt[p] ++ ;
}
3、查询操作
// 查询字符串出现的次数
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];}//返回以p结尾的单词的数量return cnt[p];
}

3.题目

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

1、 I x向集合中插入一个字符串 x;
2、 Q x询问一个字符串在集合中出现了多少次。
共有 N个操作,所有输入的字符串总长度不超过10^5 ,字符串仅包含小写英文字母。

输入格式

第一行包含整数 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>using namespace std;const int N = 100010;int son[N][26],idx,cnt[N];
char str[N];//向集合中插入一个字符串 x
void insert(char str[])
{int p = 0;for (int i = 0; str[i]; i++){int u = str[i] - 'a';//将这个字符从a-z变成 0-25if (!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];cin >> op >> str;if (op[0] == 'I') insert(str);else cout << query(str)<< endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395200.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙HarmonyOS开发:@Observed装饰器和@ObjectLink装饰器:监听嵌套类对象属性变化

文章目录 一、装饰器二、概述三、限制条件四、装饰器说明五、Toggle组件1、子组件2、接口3、ToggleType枚举4、事件 六、示例演示1、代码2、效果 一、装饰器 State装饰器&#xff1a;组件内状态Prop装饰器&#xff1a;父子单向同步Link装饰器&#xff1a;父子双向同步Provide装…

SpringBoot MybatisPlus selectOne的坑

目录 一、问题 二、问题解决 三、其他方法 一、问题 selectOne在查询多条数据时会报错&#xff0c;查询语句并不会加 limit 1。 One record is expected, but the query result is multiple records。 二、问题解决 在QueryWrapper上添加如下&#xff1a; QueryWrapper&…

支付宝开放平台竟出现一张神秘人脸!

前言 ​ 我因一个单子来到支付宝开放平台来。在将其加入书签的时候&#xff0c;我发现出现了个神秘的人脸 一张笑容明媚的脸&#xff0c;就是出现的时候不太对 正常的收藏网址 应该是显示对应log 就不继续找相关例子了 ​ 添加书签的页面&#xff0c;本该出现log的地方缺出现了…

VScode的环境编译器选择

按快捷键 Ctrl Shift P 选择即可

反向传播与梯度累积

反向传播算法&#xff1a;loss.backward()的实现细节 向前传播&#xff1a;输入数据得到预测结果。向后传播&#xff1a;计算梯度加更新参数。反向传播&#xff1a;计算梯度 计算图 计算图 有向无环图 基本运算 节点&#xff1a;变量节点 & 计算节点有向边&#xff1…

【LeetCode】48. 旋转图像

旋转图像 题目描述&#xff1a; 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在原地旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1&#xff1a; 输入&#xff1a;matrix …

【维修经验分享】可调电源输出不稳定

一、前言 从今天这期开始&#xff0c;我将在“维修经验”这个专栏中分享一些简单的电路板维修经历&#xff0c;希望能帮助大家。 二、相关信息及问题 型号&#xff1a;迈胜MS-3050。 问题&#xff1a;输出电压无法稳定下来&#xff0c;一直在跳动。这款电源估计也比较老了&…

Linux系统之ls命令的基本使用

Linux系统之ls命令的基本使用 一、ls命令介绍二、ls命令的使用帮助2.1 命令格式2.2 命令选项2.3 使用帮助 三、ls命令的基本使用3.1 列出当前目录中的所有文件和目录3.2 列出指定目录中的所有文件和目录3.3 显示文件的详细信息3.4 列出所有文件和目录3.5 显示目录本身&#xff…

【单片机毕业设计选题24105】-基于单片机的自动配料机控制系统

系统功能: 系统分为自动状态和手动状态上电默认为手动状态&#xff0c;手动状态下可以通过按键和蓝牙手动控制步进电机正反转&#xff0c; 自动状态下根据采集到的两路接近传感器信号自动控制步进电机正反转。 系统上电后&#xff0c;OLED显示“欢迎使用请稍后”&#xff0c…

C++17常用新特性介绍

目录 1、结构化绑定 2、constexpr扩展 2.1、constexpr lambda 2.2、constexpr if 2.3、constexpr string 4、if with initializer 5、std::optional 6、使用inline定义内联变量 7、std::filesystem库 8、折叠表达式 9、模板的模板参数推导 9.1、从构造函数参数推导…

前端获取视频文件宽高信息和视频时长

安装 yarn add video-metadata-thumbnails | npm install video-metadata-thumbnails引入依赖包 import { getMetadata } from video-metadata-thumbnails使用 if (file.name.includes(mp4)) {if (file) {try {console.log(file)// 获取视频的元数据const metadata await …

【微信小程序开发】——奶茶点餐小程序的制作(一)

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;开发者-曼亿点 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 曼亿点 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a…

51单片机—智能垃圾桶(定时器)

一. 定时器 1. 简介 C51中的定时器和计数器是同一个硬件电路支持的&#xff0c;通过寄存器配置不同&#xff0c;就可以将他当做定时器或者计数器使用。 确切的说&#xff0c;定时器和计数器区别是致使他们背后的计数存储器加1的信号不同。当配置为定时器使用时&#xff0c;每…

数据结构的基本概念

数据结构的基本概念 数据是什么&#xff1f; 数据 &#xff1a; 数据是信息的载体&#xff0c;是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别&#xff08;二进制0|1&#xff09;和处理的符号的集合。数据是计算机程序加工的原料。 早期计算机处理的…

【代码随想录】有序数组的平方

本博文为《代码随想录》的学习笔记&#xff0c;原文链接&#xff1a;代码随想录 题目 977. 有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&…

【物联网设备端开发】使用QEMU模拟ESP硬件运行ESP-IDF

目录 一&#xff0c;开发环境搭建 1.1 安装ESP-IDF 1.2 安装vscode插件 1.3 在ESP-IDF插件配置ESP-IDF开发配置 1.4 下载IOTDeviceSDK 设备端开发代码 1.5 通过ESP-IDF插件编译好镜像 1.6 构建QEMU docker镜像 1.7 使用QEMU容器运行镜像 二&#xff0c;搭建QEMU环境步…

PTrade常见问题系列22

反馈定义的上午7点执行run_daily函数&#xff0c;但是每周一上午都没法正常执行&#xff1f; 1、run_daily函数加载在initialize函数中&#xff0c;执行后才会创建定时任务&#xff1b; 2、由于周末会有例行重启操作&#xff0c;在重启以后拉起交易时相当于非交易日启动的交易…

C到C++——C++基础

C是一种通用的、静态类型的、跨平台的编程语言。它是在1979年由Bjarne Stroustrup创建的&#xff0c;最初是作为C语言的扩展来支持面向对象编程。 C在保留C语言的特性的同时&#xff0c;添加了许多其他的功能&#xff0c;包括类、对象、继承、多态、模板等。这使得C成为了一种…

大数据面试SQL(五):查询最近一笔有效订单

文章目录 查询最近一笔有效订单 一、题目 二、分析 三、SQL实战 四、样例数据参考 查询最近一笔有效订单 一、题目 现有订单表t5_order&#xff0c;包含订单ID&#xff0c;订单时间&#xff0c;下单用户&#xff0c;当前订单是否有效。 请查询出每笔订单的上一笔有效订…

Vue - 关于vue-kinesis 移动动画组件

Vue - 关于vue-kinesis 移动动画组件 vue-kinesis可以根据鼠标移动或滚动条来控制元素动画的动画效果&#xff1b;除此之外&#xff0c;vue-kinesis 还可以设置音频文件&#xff0c;根据音频频率来控制动画的跳动效果。 一、安装vue-kinesis Vue2版本&#xff1a; 1.安装 …