当前位置: 首页 > 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;…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...