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

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就是构造一个数字使之唯一代表一个字符串。但是为了将映射关系进行一一对应&#xff0c;也就是&#xff0c;一个字符串对应一个数字&#xff0c;那么一个数字也对应一个字符串。 用字符串Hash的目的是&#xff0c;我们如果要比较一个字符串&#xff0c;我们不用直接比…...

【java】项目部署liunx服务器的简单步骤

在Linux服务器上部署Java项目通常涉及到一系列步骤&#xff0c;下面是一个基本的部署流程&#xff0c;具体步骤可能会根据项目和服务器环境的不同而有所调整&#xff1a; 1. 准备工作&#xff1a; 1.1 安装Java环境&#xff1a; 在Linux服务器上安装Java运行环境&#xff0c;…...

深度学习笔记(五)——网络优化(1):学习率自调整、激活函数、损失函数、正则化

文中程序以Tensorflow-2.6.0为例 部分概念包含笔者个人理解&#xff0c;如有遗漏或错误&#xff0c;欢迎评论或私信指正。 截图和程序部分引用自北京大学机器学习公开课 通过学习已经掌握了主要的基础函数之后具备了搭建一个网络并使其正常运行的能力&#xff0c;那下一步我们还…...

鸿蒙开发现在就业前景怎样?

随着科技的不断进步&#xff0c;鸿蒙系统逐渐崭露头角&#xff0c;成为智能设备领域的一颗新星。作为华为自主研发的操作系统&#xff0c;鸿蒙系统拥有着广阔的市场前景和就业机会。那么&#xff0c;鸿蒙开发的就业前景究竟怎样呢&#xff1f; 一、市场需求持续增长 随着鸿蒙…...

试用统信服务器操作系统UOS 20

作者&#xff1a;田逸&#xff08;formyz&#xff09; 试用统信Linux操作系统UOS&#xff0c;想了解一下用已有的Linux经验能否轻松驾驭它。以便在某些场景下&#xff0c;可以多一种选择。本次试验在Proxmox VE 8&#xff08;以下简称PVE 8&#xff09;平台下进行&#xff0c;采…...

[情商-11]:人际交流的心理架构与需求层次模型

目录 前言&#xff1a; 一、心理架构 1.1 个体生理层 1.2 个体心理层 1.3 点对点人际交流层 1.4 社会网络层 1.5 社会价值层 二、人的需求层次模型 2.1 需求&#xff08;欲望&#xff09;层次模型 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. 链表相交 时间复杂度&#xff1a;O(N)&#xff0c;空间复杂度&#xff1a;O(1) 第一想法&#xff1a;求出两个链表长度&#xff0c;走差距步&#xff0c;再遍历找有没有相交 /*** 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&#xff0c;平均…...

Unity3d 实现直播功能(无需sdk接入)

Unity3d 实现直播功能 需要插件 :VideoCapture 插件地址(免费的就行) 原理:客户端通过 VideoCapture 插件实现推流nodejs视频流转服务进行转发,播放器实现rtmp拉流 废话不多说,直接上 CaptureSource我选择的是屏幕录制,也可以是其他源 CaptureType选择LIVE–直播形式 LiveSt…...

计算机缺失msvcr100.dll如何修复?分享五种实测靠谱的方法

在计算机系统的日常运行与维护过程中&#xff0c;我们可能会遇到一种特定的故障场景&#xff0c;即系统中关键性动态链接库文件msvcr100.dll的丢失。msvcr100.dll是Microsoft Visual C Redistributable Package的一部分&#xff0c;对于许多基于Windows的应用程序来说&#xff…...

面试宝典进阶之redis缓存面试题

R1、【初级】Redis常用的数据类型有哪些&#xff1f; &#xff08;1&#xff09;String&#xff08;字符串&#xff09; &#xff08;2&#xff09;Hash&#xff08;哈希&#xff09; &#xff08;3&#xff09;List&#xff08;列表&#xff09; &#xff08;4&#xff09;Se…...

调试(c语言)

前言&#xff1a; 我们在写程序的时候可能多多少少都会出现一些bug&#xff0c;使我们的程序不能正常运行&#xff0c;所以为了更快更好的找到并修复bug&#xff0c;使这些问题迎刃而解&#xff0c;学习好如何调试代码是每个学习编程的人所必备的技能。 1. 什么是bug&#xf…...

opencv-4.8.0编译及使用

1 编译 opencv的编译总体来说比较简单&#xff0c;但必须记住一点&#xff1a;opencv的版本必须和opencv_contrib的版本保持一致。例如opencv使用4.8.0&#xff0c;opencv_contrib也必须使用4.8.0。 进入opencv和opencv_contrib的github页面后&#xff0c;默认看到的是git分支&…...

Jmeter 性能-监控服务器

Jmeter监控Linux需要三个文件 JMeterPlugins-Extras.jar (包&#xff1a;JMeterPlugins-Extras-1.4.0.zip) JMeterPlugins-Standard.jar (包&#xff1a;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 是什么&#xff1f;Labelme 能干啥&#xff1f; Ubuntu20.04安装Labelme1.Anaconda的安装2.Labelme的安装3.Labelme的使用 概要 图像检测需要自己的数据集&#xff0c;为此需要对一些数据进行数据标注&#xff0c;这里提供了一种图像的常用标注工具——la…...

回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测(SE注意力机制)

回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测&#xff08;SE注意力机制&#xff09; 目录 回归预测 | Matlab实现SSA-CNN-LSTM-Attention麻雀优化卷积长短期记忆神经网络注意力机制多变量回归预测&#xff08;SE注意力…...

css垂直水平居中的几种实现方式

垂直水平居中的几种实现方式 一、固定宽高&#xff1a; 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;…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...