C++ 字符串哈希 || 字符串前缀哈希法
字符串Hash就是构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应,也就是,一个字符串对应一个数字,那么一个数字也对应一个字符串。
用字符串Hash的目的是,我们如果要比较一个字符串,我们不用直接比较字符串,而是比较它对应映射的数字,这样子就知道两个“子串”是否相等。从而达到,子串的Hash值的时间为 O(1),进而可以利用“空间换时间”来节省时间复杂的。
#######################################
给定一个长度为 n
的字符串,再给定 m
个询问,每个询问包含四个整数 l1,r1,l2,r2
,请你判断 [l1,r1]
和 [l2,r2]
这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数 n
和 m
,表示字符串长度和询问次数。
第二行包含一个长度为 n
的字符串,字符串中只包含大小写英文字母和数字。
接下来 m
行,每行包含四个整数 l1,r1,l2,r2
,表示一次询问所涉及的两个区间。
注意,字符串的位置从 1
开始编号。
输出格式
对于每个询问输出一个结果,如果两个字符串子串完全相同则输出 Yes,否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤105
输入样例:
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例:
Yes
No
Yes
关键点:
字符串哈希值的计算:通过前缀哈希值,可以在常数时间内计算任意子串的哈希值。在这里,使用了 get 函数来计算 [l, r] 子串的哈希值。
进制选择:选择一个适当的进制是关键,这里使用了常用的质数 131( 常用P 还可以= 133313)。质数的选择可以减小哈希冲突的可能性。前缀哈希值的快速计算:通过累积进制的幂,可以在常数时间内计算前缀哈希值。这里使用了 p 数组存储进制的幂,h 数组存储前缀哈希值。字符串比较:通过比较两个子串的哈希值是否相等,可以在常数时间内完成字符串的比较。这在一些算法中能够提高效率,例如字符串的快速匹配等。
#include <iostream>using namespace std;typedef unsigned long long ULL; // 使用 unsigned long long 类型表示哈希值const int N = 100010, P = 131; // N 表示字符串长度的最大值,P 是选择的哈希进制int n, m;
ULL h[N], p[N]; // h 存储前缀哈希值,p 存储进制的幂
char str[N]; // 输入的字符串ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l + 1]; // 计算字符串 [l, r] 的哈希值,使用前缀哈希值的差值表示子串哈希值
}int main()
{scanf("%d%d%s", &n, &m, str + 1);p[0] = 1;for(int i = 1; i <= n; i ++ ){p[i] = p[i - 1] * P; // 计算进制的幂h[i] = h[i - 1] * P + str[i]; // 计算前缀哈希值}while(m -- ){int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if(get(l1, r1) == get(l2, r2)) printf("Yes\n"); // 比较两个子串的哈希值是否相等else printf("No\n");}return 0;
}
代码中:
h[i] = h[i - 1] * P + str[i];是字符串哈希的递推计算方式,称为Rolling Hash。
在这个式子中,h[i] 表示字符串的前 i 个字符的哈希值。它通过前一个状态 h[i-1],乘以进制 P,再加上当前字符 str[i] 的 ASCII 码,得到当前状态 h[i]。
这个计算过程实际上是一种累积计算,每次迭代都基于前一个状态进行更新。由于使用了进制 P,每一次迭代都相当于在前一个状态的基础上左移一位,并加上新字符的贡献。
这样计算的好处在于,每次只需要常数时间就能够更新哈希值,使得整个字符串的哈希值的计算复杂度是线性的。在很多字符串匹配、子串比较的算法中,这种哈希计算方式可以提高效率。需要注意的是,为了避免整数溢出,通常需要选择一个适当的大质数作为进制 P。
相关文章:
C++ 字符串哈希 || 字符串前缀哈希法
字符串Hash就是构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应,也就是,一个字符串对应一个数字,那么一个数字也对应一个字符串。 用字符串Hash的目的是,我们如果要比较一个字符串,我们不用直接比…...
【java】项目部署liunx服务器的简单步骤
在Linux服务器上部署Java项目通常涉及到一系列步骤,下面是一个基本的部署流程,具体步骤可能会根据项目和服务器环境的不同而有所调整: 1. 准备工作: 1.1 安装Java环境: 在Linux服务器上安装Java运行环境,…...
深度学习笔记(五)——网络优化(1):学习率自调整、激活函数、损失函数、正则化
文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解,如有遗漏或错误,欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 通过学习已经掌握了主要的基础函数之后具备了搭建一个网络并使其正常运行的能力,那下一步我们还…...
鸿蒙开发现在就业前景怎样?
随着科技的不断进步,鸿蒙系统逐渐崭露头角,成为智能设备领域的一颗新星。作为华为自主研发的操作系统,鸿蒙系统拥有着广阔的市场前景和就业机会。那么,鸿蒙开发的就业前景究竟怎样呢? 一、市场需求持续增长 随着鸿蒙…...
试用统信服务器操作系统UOS 20
作者:田逸(formyz) 试用统信Linux操作系统UOS,想了解一下用已有的Linux经验能否轻松驾驭它。以便在某些场景下,可以多一种选择。本次试验在Proxmox VE 8(以下简称PVE 8)平台下进行,采…...
[情商-11]:人际交流的心理架构与需求层次模型
目录 前言: 一、心理架构 1.1 个体生理层 1.2 个体心理层 1.3 点对点人际交流层 1.4 社会网络层 1.5 社会价值层 二、人的需求层次模型 2.1 需求(欲望)层次模型 2.2 基因与人需求之间的关系 2.3 个体生理需求 2.4 个体的心理需求…...
【.NET Core】Lazy<T> 实现延迟加载详解
【.NET Core】Lazy 实现延迟加载详解 文章目录 【.NET Core】Lazy<T> 实现延迟加载详解一、概述二、Lazy<T>是什么三、Lazy基本用法3.1 构造时使用默认的初始化方式3.2 构造时使用指定的委托初始化 四、Lazy.Value使用五、Lazy扩展用法5.1 实现延迟属性5.2 Lazy实现…...
坑记(HttpInputMessage)
一、背景知识 public interface HttpInputMessage extends HttpMessage Represents an HTTP input message, consisting of headers and a readable body.Typically implemented by an HTTP request on the server-side, or a response on the client-side.Since: 3.0 Author:…...
day04打卡
day04打卡 面试题 02.07. 链表相交 时间复杂度:O(N),空间复杂度:O(1) 第一想法:求出两个链表长度,走差距步,再遍历找有没有相交 /*** Definition for singly-linked list.* struct ListNode {* int…...
语义分割miou指标计算详解
文章目录 1. 语义分割的评价指标2. 混淆矩阵计算2.1 np.bincount的使用2.2 混淆矩阵计算 3. 语义分割指标计算3.1 IOU计算方式1(推荐)方式2 3.2 Precision 计算3.3 总体的Accuracy计算3.4 Recall 计算3.5 MIOU计算 参考 MIoU全称为Mean Intersection over Union,平均…...
Unity3d 实现直播功能(无需sdk接入)
Unity3d 实现直播功能 需要插件 :VideoCapture 插件地址(免费的就行) 原理:客户端通过 VideoCapture 插件实现推流nodejs视频流转服务进行转发,播放器实现rtmp拉流 废话不多说,直接上 CaptureSource我选择的是屏幕录制,也可以是其他源 CaptureType选择LIVE–直播形式 LiveSt…...
计算机缺失msvcr100.dll如何修复?分享五种实测靠谱的方法
在计算机系统的日常运行与维护过程中,我们可能会遇到一种特定的故障场景,即系统中关键性动态链接库文件msvcr100.dll的丢失。msvcr100.dll是Microsoft Visual C Redistributable Package的一部分,对于许多基于Windows的应用程序来说ÿ…...
面试宝典进阶之redis缓存面试题
R1、【初级】Redis常用的数据类型有哪些? (1)String(字符串) (2)Hash(哈希) (3)List(列表) (4)Se…...
调试(c语言)
前言: 我们在写程序的时候可能多多少少都会出现一些bug,使我们的程序不能正常运行,所以为了更快更好的找到并修复bug,使这些问题迎刃而解,学习好如何调试代码是每个学习编程的人所必备的技能。 1. 什么是bug…...
opencv-4.8.0编译及使用
1 编译 opencv的编译总体来说比较简单,但必须记住一点:opencv的版本必须和opencv_contrib的版本保持一致。例如opencv使用4.8.0,opencv_contrib也必须使用4.8.0。 进入opencv和opencv_contrib的github页面后,默认看到的是git分支&…...
Jmeter 性能-监控服务器
Jmeter监控Linux需要三个文件 JMeterPlugins-Extras.jar (包:JMeterPlugins-Extras-1.4.0.zip) JMeterPlugins-Standard.jar (包:JMeterPlugins-Standard-1.4.0.zip) ServerAgent-2.2.3.zip 1、Jemter 安装插件 在插件管理中心的搜索Servers Perform…...
Excel学习
文章目录 学习链接Excel1. Excel的两种形式2. 常见excel操作工具3.POI1. POI的概述2. POI的应用场景3. 使用1.使用POI创建excel2.创建单元格写入内容3.单元格样式处理4.插入图片5.读取excel并解析图解POI 4. 基于模板输出POI报表5. 自定义POI导出工具类ExcelAttributeExcelExpo…...
【技能---labelme软件的安装及其使用--ubuntu】
文章目录 概要Labelme 是什么?Labelme 能干啥? Ubuntu20.04安装Labelme1.Anaconda的安装2.Labelme的安装3.Labelme的使用 概要 图像检测需要自己的数据集,为此需要对一些数据进行数据标注,这里提供了一种图像的常用标注工具——la…...
回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测(SE注意力机制)
回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测(SE注意力机制) 目录 回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测(SE注意力…...
css垂直水平居中的几种实现方式
垂直水平居中的几种实现方式 一、固定宽高: 1、定位 margin-top margin-left .box-container{position: relative;width: 300px;height: 300px;}.box-container .box {width: 200px; height: 100px;position: absolute; left: 50%; top: 50%;margin-top: -50px;…...
告别手推雅可比!用Ceres自动求导搞定SLAM中的BA优化(附完整代码)
告别手推雅可比!用Ceres自动求导搞定SLAM中的BA优化(附完整代码) 在视觉SLAM系统的开发中,Bundle Adjustment(BA)优化是提升定位与建图精度的关键环节。传统实现需要手动推导复杂的雅可比矩阵,不…...
Spring PetClinic实战解析:从单体应用到云原生部署的5大架构亮点
Spring PetClinic实战解析:从单体应用到云原生部署的5大架构亮点 【免费下载链接】spring-petclinic A sample Spring-based application 项目地址: https://gitcode.com/gh_mirrors/sp/spring-petclinic 你是否遇到过这样的困境:在学习Spring框架…...
基于spring和vue的企业原材料库存盘点食品厂管理系统
目录技术选型与架构设计核心功能模块划分数据库设计要点关键技术实现前端交互优化系统安全措施测试与部署方案扩展性设计项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作技术选型与架构设计 后端采用Spring Boot框架࿰…...
单片机通用按键处理模块设计与实现
单片机通用按键处理模块设计与实现1. 项目概述1.1 模块功能特性本按键处理模块为单片机系统提供了一套完整的按键事件处理解决方案,具有以下核心功能:基础按键检测:支持按下(PRESS)和释放(RELEASE)事件检测高级触发模式:长按触发(…...
数电课设实战:从555定时器到74LS190,手把手搭建一个密码锁系统
1. 密码锁系统设计概述 第一次接触数字电路课设时,我和大多数同学一样,面对一堆芯片和电路图完全无从下手。直到教授建议从密码锁这个经典项目入手,我才发现原来数电可以这么有趣。这个系统最精妙的地方在于,它把课本上枯燥的理论…...
YOLO_World+SAM+GraspNet在mujoco中的抓取仿真实战:从环境搭建到代码运行
YOLO_WorldSAMGraspNet在MuJoCo中的抓取仿真实战:从环境搭建到代码运行 在机器人抓取仿真领域,结合YOLO_World、SAM(Segment Anything Model)和GraspNet三大前沿技术,能够在MuJoCo物理引擎中实现高度逼真的物体识别、分…...
科哥CAM++镜像入门指南:快速搭建中文语音识别系统
CAM镜像入门指南:快速搭建中文语音识别系统 1. 系统概述 CAM说话人识别系统是一个基于深度学习的声纹识别工具,由科哥封装为易用的Docker镜像。它能快速判断两段语音是否来自同一说话人,并提取语音特征向量,适用于身份验证、语音…...
OpenClaw技能开发指南:为ollama-QwQ-32B编写自定义模块
OpenClaw技能开发指南:为ollama-QwQ-32B编写自定义模块 1. 为什么需要自定义技能开发 上周我需要每天手动查询三个城市的天气数据来生成日报,这种重复劳动让我开始思考:能否让OpenClaw帮我自动完成?当我发现现有的天气技能包都不…...
夜间自动化利器:OpenClaw+nanobot定时执行爬虫任务
夜间自动化利器:OpenClawnanobot定时执行爬虫任务 1. 为什么选择OpenClaw做夜间自动化 凌晨三点,我的电脑屏幕突然亮了起来。这不是灵异事件,而是OpenClaw正在执行我预设的爬虫任务——收集行业数据、清洗整理、存入数据库,整个…...
TuShare实战(二)高效构建多股数据面板
1. 为什么需要多股数据面板 做量化投资的朋友都知道,数据准备是最基础也最耗时的环节。想象一下,你正在研究一个投资策略,需要同时分析5只股票的历史走势。如果每次都要单独获取、整理每只股票的数据,那效率实在太低了。这就是为什…...
