当前位置: 首页 > 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的RenderJS为你的APP手势和动画性能提速(实战解析)

告别卡顿&#xff01;用UniApp的RenderJS为你的APP手势和动画性能提速&#xff08;实战解析&#xff09; 在移动应用开发中&#xff0c;流畅的用户体验往往决定了产品的成败。当你在UniApp框架下开发APP时&#xff0c;是否遇到过这样的场景&#xff1a;地图拖拽时出现明显延迟&…...

Docker Compose 多服务编排实战:从零搭建微服务架构

Docker Compose 多服务编排实战&#xff1a;从零搭建微服务架构 目录 为什么需要 Docker Compose&#xff1f;实战项目架构环境准备核心服务搭建高级特性&#xff1a;负载均衡与服务发现日志集中管理&#xff08;EFK 栈&#xff09;生产环境最佳实践常见问题排查 为什么需要 …...

Realistic Vision V5.1镜像部署实操:解决‘模型路径不存在’异常的完整排查链

Realistic Vision V5.1镜像部署实操&#xff1a;解决‘模型路径不存在’异常的完整排查链 1. 引言&#xff1a;从“模型路径不存在”说起 如果你在部署Realistic Vision V5.1虚拟摄影棚时&#xff0c;满怀期待地启动程序&#xff0c;结果却在控制台看到一行冰冷的“模型路径不…...

微信单向好友检测终极指南:如何一键找出并清理删除你的微信好友

微信单向好友检测终极指南&#xff1a;如何一键找出并清理删除你的微信好友 【免费下载链接】WechatRealFriends 微信好友关系一键检测&#xff0c;基于微信ipad协议&#xff0c;看看有没有朋友偷偷删掉或者拉黑你 项目地址: https://gitcode.com/gh_mirrors/we/WechatRealFr…...

全网资源嗅探下载神器:轻松获取视频音频资源的终极指南

全网资源嗅探下载神器&#xff1a;轻松获取视频音频资源的终极指南 【免费下载链接】res-downloader 资源下载器、网络资源嗅探&#xff0c;支持微信视频号下载、网页抖音无水印下载、网页快手无水印视频下载、酷狗音乐下载等网络资源拦截下载! 项目地址: https://gitcode.co…...

从镜像到实战:星图OpenClaw+Qwen3-32B完整链路

从镜像到实战&#xff1a;星图OpenClawQwen3-32B完整链路 1. 为什么选择OpenClawQwen3-32B组合 去年冬天&#xff0c;当我第一次尝试用AI自动化处理周报时&#xff0c;发现公有云方案总在数据隐私和功能定制上让我束手束脚。直到遇见星图平台的OpenClaw镜像与Qwen3-32B组合&a…...

ESP WiFi中继器终极配置指南:从零开始打造智能无线网络扩展器

ESP WiFi中继器终极配置指南&#xff1a;从零开始打造智能无线网络扩展器 【免费下载链接】esp_wifi_repeater A full functional WiFi Repeater (correctly: a WiFi NAT Router) 项目地址: https://gitcode.com/gh_mirrors/es/esp_wifi_repeater 想要轻松扩展WiFi覆盖范…...

手把手调试Android触摸反馈:用Systrace和日志追踪小圆点显示的全过程

Android触摸反馈调试实战&#xff1a;从Systrace到Logcat的全链路追踪 在移动应用开发中&#xff0c;触摸反馈的准确性和即时性直接影响用户体验。当用户手指接触屏幕时&#xff0c;那个跟随指尖跳动的小圆点看似简单&#xff0c;背后却隐藏着复杂的系统级交互。本文将带你深入…...

6_Harness驾驭工程可靠性层:混沌工程与服务可靠性管理

6_Harness驾驭工程可靠性层&#xff1a;混沌工程与服务可靠性管理 关键字&#xff1a; Chaos Engineering、混沌工程、SRM、服务可靠性管理、SLI、SLO、错误预算、韧性评分、故障模拟、事件响应、事后分析、韧性验证、自动故障注入、最小爆炸半径、Datadog、New Relic、Prometh…...

轻量级工具G-Helper:一站式解决ROG游戏本色彩配置异常问题

轻量级工具G-Helper&#xff1a;一站式解决ROG游戏本色彩配置异常问题 【免费下载链接】g-helper Lightweight Armoury Crate alternative for Asus laptops. Control tool for ROG Zephyrus G14, G15, G16, M16, Flow X13, Flow X16, TUF, Strix, Scar and other models 项目…...