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

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

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;供调用如何按…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...