字符串哈希(c++)

1、定义

字符串哈希把不同的字符串映射成不同的整数


1.1、规则

1、把字符串映射成一个P进制数字

对于一个长度为n的字符串s

这样定义Hash函数:

例如:字符串abc,其哈希函数值为ap^2 + bp^1 + c;

即97 * 131^2 + 98 * 131^1 + 99;

2、两个字符串不一样,hash函数值却是一样,这样的现象叫哈希碰撞(冲突)

3、哈希碰撞的方法:

巧妙设置P和M的值,保证P与M互质。

P通常取质数131或13331

M通常取大整数2^64,把哈希函数值h定义为ULL,超过则自动溢出,等价于取模。因为ULL的上界就是2 ^ 64


 

2、实现


这里说一下区间和这个公式:

可以看到整个公式可以理解为将h[3] *p^2正好是把第三项的前缀和平方,这样拿第5项前缀和 - 第三项前缀和 正好就等于DE

也可以看成是ABCDE - ABC00这样。


代码模板:


3、例题841. 字符串哈希 - AcWing题库

AC代码:
#include<iostream>
#include<cstring>using namespace std;typedef unsigned long long ULL;
const int N = 1e5+10,P = 131;
ULL h[N],p[N];//h[]存映射值,p[]存P进制的值
int n,m;
char s[N];
//计算1~i的哈希值
ULL get(int l,int r)
{return h[r] - h[l-1] * p[r-l+1];    
}int main()
{scanf("%d %d%s", &n, &m,s+1);h[0] = 0,p[0] = 1;//预处理哈希值的前缀和for(int i=1;i<=n;i++){//p[i] = P^ip[i] = p[i-1] * P;//求一下P进制h[i] = h[i-1] * P + s[i];//求出前缀和下的哈希值}while (m -- ){int l1,r1,l2,r2;scanf("%d %d %d %d",&l1,&r1,&l2,&r2);//判断两个子串是否xiang'oif(get(l1,r1) == get(l2,r2)) printf("Yes\n");else printf("No\n");}return 0;
}

上述笔记根据B站董晓算法记录~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284479.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【计算机网络篇】数据链路层(3)差错检测

文章目录 &#x1f95a;误码&#x1f354;两种常见的检错技术⭐奇偶校验⭐循环冗余校验&#x1f388;例子 &#x1f95a;误码 误码首先介绍误码的相关概念 &#x1f354;两种常见的检错技术 ⭐奇偶校验 奇校验是在待发送的数据后面添加1个校验位&#xff0c;使得添加该校验…

C++|类封装、类的分文件编写练习:设计立方体类、点和圆的关系

文章目录 练习案例1&#xff1a;设计立方体类CPP代码 练习案例2:点和圆的关系CPP代码 代码总结类的分文件编写 练习案例1&#xff1a;设计立方体类 设计立方体类(Cube) 求出立方体的面积和体积 分别用全局函数和成员函数判断两个立方体是否相等。 CPP代码 class Cube { pub…

GPT4.0

GPT4.0 支持官网所有功能以及所有第三方GPTS&#xff0c;完全同步官网。无需魔法&#xff0c;填写授权码直达官网。全天超18小时维护&#xff0c;无需担心不稳定。没有永久卡&#xff0c;3.5免费提供&#xff0c;4.0可以按需下单即可&#xff0c;不存在跑路。 需要的联系

详细安装步骤:vue.js 三种方式安装(vue-cli)

Vue.js&#xff08;读音 /vjuː/, 类似于 view&#xff09;是一个构建数据驱动的 web 界面的渐进式框架。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。它不仅易于上手&#xff0c;还便于与第三方库或既有项目整合。 三种 Vue.js 的安装方法&…

unity 多屏幕操作

想了解基础操作请移步&#xff1a;&#xff08;重点是大佬写的好&#xff0c;这里就不再赘述&#xff09; Unity 基础 之 使用 Display 简单的实现 多屏幕显示的效果_unity display-CSDN博客 在panel上也可以通过获取 Canvas&#xff0c;来达到切换多屏幕的操作&#xff0c; …

Flutter-仿携程首页类型切换

效果 唠叨 闲来无事&#xff0c;不小心下载了携程app&#xff0c;还幻想可以去旅游一番&#xff0c;奈何自己运气不好&#xff0c;自从高考时第一次吹空调导致自己拉肚子考试&#xff0c;物理&#xff0c;数学考了一半就交卷&#xff0c;英语2B铅笔除了问题&#xff0c;导致原…

行政工作常用表格

企业管制制度大全https://www.chuandao100.com/279.html

JVM垃圾收集器你会选择吗?

目录 一、Serial收集器 二、ParNew收集器 三、Paralle Scavenge 四、Serial Old 五、Parallel Old 六、CMS收集器 6.1 CMS对处理器资源非常敏感 6.2 CMS容易出现浮动垃圾 6.3 产生内存碎片 七、G1 收集器 八、如何选择合适的垃圾收集器 JVM 垃圾收集器是Java虚…

生成模型概述

文章目录 生成模型概述一、生成模型类型二、生成对抗网络&#xff08;GANs&#xff09;三、自回归模型&#xff08;Autoregressive Models&#xff09;四、扩散模型&#xff08;Diffusion Models&#xff09;五、流模型&#xff08;Flow-based Models&#xff09;参考 生成模型…

【数据分享】1929-2023年全球站点的逐日平均海平面压力(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、能见度等指标&#xff0c;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全球气象站…

CPP容器vector和list,priority_queue定义比较器

#include <iostream> #include <bits/stdc.h> using namespace std; struct VecCmp{bool operator()(int& a,int& b){return a>b;/*** 对于vector和list容器&#xff0c;这里写了&#xff1e;就是从大到小* 对于priority_queue容器&#xff0c;这里写…

【阅读论文】When Large Language Models Meet Vector Databases: A Survey

摘要 本调查探讨了大型语言模型&#xff08;LLM&#xff09;和向量数据库&#xff08;VecDB&#xff09;之间的协同潜力&#xff0c;这是一个新兴但迅速发展的研究领域。随着LLM的广泛应用&#xff0c;出现了许多挑战&#xff0c;包括产生虚构内容、知识过时、商业应用成本高昂…

【算法与数据结构】 C语言实现单链表队列详解

文章目录 &#x1f4dd;队列&#x1f320; 数据结构设计&#x1f309;初始化队列函数 &#x1f320;销毁队列函数&#x1f309;入队函数 &#x1f320;出队函数&#x1f309;获取队首元素函数 &#x1f320;获取队尾元素函数&#x1f309; 判断队列是否为空函数&#x1f309;获…

如何让uni-app开发的H5页面顶部原生标题和小程序的顶部标题不一致?

如何让标题1和标题2不一样&#xff1f; 修改根目录下的App.vue&#xff08;核心代码如下&#xff09; <script>export default {onLaunch() {// 监听各种跳转----------------------------------------[navigateTo, redirectTo, reLaunch, switchTab, navigateBack, ].…

Leetcode 226. 翻转二叉树

心路历程&#xff1a; 翻转一瞬间没什么思路&#xff0c;其实就是挨个把每个结点的左右子树都翻转了。主要不要按照左右子树去思考&#xff0c;要按照结点去思考。 翻转既可以从上到下翻转&#xff08;前序遍历&#xff09;&#xff0c;也可以从下到上翻转&#xff08;后序遍历…

等保测评-Windows服务器

安全计算环境 身份鉴别 a)应对登录的用户进行身份标识和鉴别&#xff0c;身份标识具有唯一性&#xff0c;身份鉴别信息具有复杂度要求并定期更换 winr //运行 secpol.msc //本地安全策略&#xff0c;点击账户策略中的密码策略 注意修改的时候确保当前密码是满足条件的 b)应…

应急响应-Linux(1)

应急响应-Linux(1) 黑客的IP地址 思路&#xff1a; 一般系统中马之后会有进程连接黑客的主机&#xff0c;可以使用netstat -anpt查看下当前进程的连接&#xff0c;此处查看到没有后 &#xff0c;可以从系统服务开始查找&#xff0c;系统的服务日志一般都会保存相关访问信息&…

idea 没有代码提示解决方法

itellij idea 没有代码提示解决方法 今天写代码发现没有代码提示了&#xff0c;很难受。 直接上解决方法 设置 File-Settings-Editor-General-Code Completion&#xff1a;勾选Show suggestrions as you type 我的是这个问题&#xff0c;勾选上就ok了 取消节能模式 如果…

智慧公园:AI智能分析网关V4城市公园视频智能监管方案

一、背景分析 随着天气渐渐转暖&#xff0c;城市公园的花卉也逐渐盛开&#xff0c;春暖花开时节&#xff0c;前往公园赏花游玩的城市居民也渐渐多起来&#xff0c;因此安全问题也成为相关监管部门的重要管理任务之一。随着科技的不断进步&#xff0c;智能监控技术已经成为现代…

WPS制作甘特图

“ 甘特图&#xff08;Gantt chart&#xff09;又称为横道图、条状图&#xff08;Bar chart&#xff09;&#xff0c;通过条状图来显示项目、进度和其他时间相关的系统进展的内在关系随着时间进展的情况。” 设置基础样式 设置行高 设置宽度 准备基础数据 计算持续时间 …