news 2026/6/20 2:00:12

信奥赛C++提高组csp-s之哈希

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
信奥赛C++提高组csp-s之哈希

信奥赛C++提高组csp-s之哈希

1. 什么是哈希

哈希（Hash）是将任意长度的输入通过哈希函数映射为固定长度的输出（哈希值）的过程。在字符串哈希中，我们将字符串转换为一个整数，以便：

  • 快速比较字符串是否相等
  • 快速计算子串的哈希值
  • 支持字符串的快速匹配和查找

哈希的特点：

  1. 确定性：相同字符串总是产生相同的哈希值
  2. 高效性：计算速度快
  3. 冲突可能性：不同字符串可能产生相同哈希值（哈希碰撞）
2. 如何构造字符串哈希
2.1 基本思想

将字符串看作一个P进制数，每个字符对应一个数字（通常是ASCII码），然后对一个大数M取模。

2.2 公式推导

对于一个长度为n的字符串s，我们可以将其视为P进制数：

hash(s) = (s[0] * P^(n-1) + s[1] * P^(n-2) + ... + s[n-1]) mod M
2.3 常用的参数选择
  • P（进制基数）：通常选择质数，如131, 13331等
  • M（模数）：选择大质数，如1e9+7, 1e9+9，或者使用自然溢出（2^64）
2.4 基础实现
#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongULL;// 利用自然溢出作为模数constintN=100010;constULL P=131;// 经验值，131或13331// 计算字符串的哈希值ULLcomputeHash(conststring&s){ULL h=0;for(charc:s){h=h*P+c;// 利用unsigned long long自然溢出}returnh;}intmain(){string s="hello";ULL hashValue=computeHash(s);cout<<"字符串 '"<<s<<"' 的哈希值: "<<hashValue<<endl;return0;}
3. 滚动哈希优化（前缀哈希）
3.1 为什么需要滚动哈希？

直接计算每个子串的哈希值需要O(n)时间，通过预处理前缀哈希，我们可以在O(1)时间内计算任意子串的哈希值。

3.2 实现步骤
  1. 预处理前缀哈希数组h
  2. 预处理P的幂次数组p
  3. 通过公式计算任意子串哈希值

案例研究（子串判重）

题目描述

给定一个含有 26 个小写英文字母的字符串。有 n 次询问，每次给出 2个区间，请问这两个区间里的子字符串是否一样？

输入

第一行输入一个非空字符串 s 。

第二行一个数字 n，表示 n次询问。

接下来 n行，每行四个数字 l1,r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从 1开始编号。

数据范围：

1 ≤ n , l1 , r1 , l2 , r2 ≤10 6 10^6106

输出

对于每次询问，输出一行表示结果。

如果两个子串完全一样，输出YES，否则输出NO。

样例输入

abcdebcd 3 2 3 6 7 1 3 4 6 2 5 2 5

样例输出

YES NO YES

思路分析

这个问题需要通过字符串哈希技术来实现O(1)时间复杂度的子串比较。核心思想是将字符串转换为数值（哈希值），通过比较哈希值来判断子串是否相等。

关键技术点

  1. 字符串哈希原理：

    • 将字符串看作一个P进制的数（P通常取131或13331）
    • 预处理每个前缀的哈希值和P的幂次
    • 通过前缀哈希值的组合可以在O(1)时间内计算任意子串的哈希值

  2. 哈希公式：

    • 前缀哈希：h[i] = h[i-1] * P + s[i]
    • 子串哈希：hash(l,r) = h[r] - h[l-1] * p[r-l+1]

  3. 避免哈希冲突：

    • 使用unsigned long long自然溢出（自动对2 64 2^{64}264取模）
    • 也可以使用双哈希或更大的质数模数

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongULL;// 使用unsigned long long自然溢出作为哈希值constintN=1e6+10;// 最大字符串长度+10constULL P=131;// 哈希基数，通常取131或13331ULL h[N];// h[i]存储前i个字符的哈希值ULL p[N];// p[i]存储P的i次幂，用于快速计算子串哈希chars[N];// 存储输入字符串（从索引1开始）intn;// 询问次数/** * 计算子串[l, r]的哈希值 * 公式：hash(l, r) = h[r] - h[l-1] * p[r-l+1] */ULLgetHash(intl,intr){returnh[r]-h[l-1]*p[r-l+1];}intmain(){// 读入字符串，从索引1开始存储scanf("%s",s+1);// 初始化p[0] = 1（P^0 = 1）p[0]=1;// 获取字符串长度intlen=strlen(s+1);// 预处理哈希数组和幂次数组for(inti=1;i<=len;i++){// p[i] = P^i，用于后续计算p[i]=p[i-1]*P;// h[i] = h[i-1] * P + s[i]的编码值// s[i]-'a'+1：将字符a-z映射为1-26h[i]=h[i-1]*P+(s[i]-'a'+1);}// 读入询问次数cin>>n;// 处理每个询问while(n--){intl1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);// 比较两个子串的哈希值if(getHash(l1,r1)==getHash(l2,r2)){printf("YES\n");}else{printf("NO\n");}}return0;}

功能分析

1.时间复杂度
  • 预处理：O(n)，n为字符串长度
  • 每次查询：O(1)
  • 总复杂度：O(n + q)，其中q为查询次数
2.空间复杂度
  • O(n)，用于存储前缀哈希值和幂次数组
3.算法正确性保证
  • 哈希冲突概率：使用自然溢出（对2^64取模）和合适的基数P，冲突概率极低
  • 数值范围：unsigned long long范围[0, 2^64-1]，足够容纳哈希值
4.边界情况处理
  • 字符串长度为1
  • 查询区间为整个字符串
  • 多个相同查询
  • 区间完全重合（如样例中的2 5 2 5）
5.优化思考
  • 可以添加长度检查快速排除不等长的情况
  • 对于大数据集，可以使用双哈希进一步降低冲突概率
// 使用两个不同的P和MOD，降低哈希冲突概率constintP1=131,P2=13331;constintMOD1=1e9+7,MOD2=1e9+9;

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}
  • 一、CSP信奥赛C++通关学习视频课：
    • C++语法基础
    • C++语法进阶
    • C++算法
    • C++数据结构
    • CSP信奥赛数学
    • CSP信奥赛STL
  • 二、CSP信奥赛C++竞赛拿奖视频课：
    • 信奥赛csp-j初赛高频考点解析
    • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
  • 三、csp高频考点知识详解及案例实践：
    • CSP信奥赛C++之动态规划
    • CSP信奥赛C++之标准模板库STL
    • 信奥赛C++提高组csp-s知识详解及案例实践
  • 四、考级、竞赛刷题题单及题解：
    • GESP C++考级真题题解
    • CSP信奥赛C++初赛及复赛高频考点真题解析
    • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转


2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/6/18 11:03:48

儿童疫苗照怎么压缩到300kb？宝宝防疫本照片压缩全解析

给宝宝办理疫苗本、准备入学健康凭证时&#xff0c;不少家长都会卡在照片环节&#xff1a;要么照片太大超过300kb无法上传&#xff0c;要么压缩后模糊看不清&#xff0c;连疫苗记录都没法清晰呈现。儿童疫苗照作为宝宝防疫本和入学健康凭证的关键材料&#xff0c;有明确规格要求…

作者头像 李华
网站建设 2026/6/2 4:27:29

智能抠图Rembg实战：透明Logo制作的详细教程

智能抠图Rembg实战&#xff1a;透明Logo制作的详细教程 1. 引言 1.1 业务场景描述 在品牌设计、UI/UX开发和数字内容创作中&#xff0c;透明背景的Logo图像是不可或缺的基础素材。传统手动抠图依赖Photoshop等专业工具&#xff0c;耗时耗力且对操作者技能要求高。随着AI技术…

作者头像 李华
网站建设 2026/6/19 21:40:53

模型部署实战：Rembg抠图服务搭建指南

模型部署实战&#xff1a;Rembg抠图服务搭建指南 1. 引言 1.1 智能万能抠图 - Rembg 在图像处理与内容创作领域&#xff0c;精准、高效的背景去除技术一直是核心需求之一。无论是电商商品图精修、社交媒体素材制作&#xff0c;还是AI生成内容&#xff08;AIGC&#xff09;中…

作者头像 李华
网站建设 2026/6/10 15:12:18

Spring Boot整合Nacos：从入门到精通

引言 在微服务架构中&#xff0c;服务注册与发现、配置管理是两个核心组件。Nacos作为阿里巴巴开源的一站式服务治理平台&#xff0c;提供了服务发现、配置管理和动态DNS服务等功能。本文将详细介绍如何在Spring Boot项目中整合Nacos&#xff0c;实现服务注册与发现以及配置中…

作者头像 李华
网站建设 2026/6/13 19:10:46

2026全网最全网络安全学习路线！整理了一个月！

正文&#xff1a; 禁止废话&#xff0c;先看学习路线图&#xff1b; 在这个圈子技术门类中&#xff0c;工作岗位主要有以下三个方向&#xff1a; 安全研发安全研究&#xff1a;二进制方向安全研究&#xff1a;网络渗透方向 下面逐一说明一下。 第一个方向&#xff1a;安全研…

作者头像 李华
网站建设 2026/6/15 15:05:52

Rembg批量处理教程：高效完成大量图片抠图

Rembg批量处理教程&#xff1a;高效完成大量图片抠图 1. 引言 1.1 智能万能抠图 - Rembg 在图像处理领域&#xff0c;背景去除是一项高频且繁琐的任务。无论是电商商品图精修、证件照制作&#xff0c;还是设计素材提取&#xff0c;传统手动抠图耗时耗力&#xff0c;而通用自…

作者头像 李华