news 2026/6/10 16:04:27

信奥赛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/10 14:29:05

提升数据处理效率：Qwen2.5-7B实现精准结构化输出

提升数据处理效率&#xff1a;Qwen2.5-7B实现精准结构化输出 在现代AI应用中&#xff0c;大语言模型&#xff08;LLM&#xff09;的推理结果往往以自由文本形式返回&#xff0c;这虽然灵活&#xff0c;但对后续的数据解析、系统集成和自动化流程带来了巨大挑战。尤其是在批量处…

作者头像 李华
网站建设 2026/5/21 9:34:52

AI视觉感知开发：MiDaS模型边缘计算部署方案

AI视觉感知开发&#xff1a;MiDaS模型边缘计算部署方案 1. 引言&#xff1a;AI 单目深度估计的现实意义 在智能硬件与边缘计算快速发展的今天&#xff0c;如何让设备“看懂”三维世界成为关键挑战。传统深度感知依赖双目摄像头、激光雷达等昂贵传感器&#xff0c;而单目深度估…

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

智能万能抠图Rembg部署指南：从安装到应用完整流程

智能万能抠图Rembg部署指南&#xff1a;从安装到应用完整流程 1. 引言 1.1 技术背景与趋势 随着AI图像处理技术的快速发展&#xff0c;自动去背景&#xff08;Image Matting / Background Removal&#xff09;已成为电商、设计、内容创作等领域的刚需。传统手动抠图效率低&a…

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

软件测试面试爱问的数据库的概念和分类

数据库概念 数据库是指长期存储在计算机内&#xff0c;有组织的数据集合。数据库简单说就是一个存数据的地方。 数据库的分类 1 关系型数据库 讲数据间的关系以数据库表的形式加以表达&#xff0c;并将数据存储到表格中&#xff0c;便于查询。 常见的关系型数据库&#xf…

作者头像 李华
网站建设 2026/6/10 14:26:09

轻松实现长文本生成｜基于Qwen2.5-7B镜像的结构化输出实践

轻松实现长文本生成&#xff5c;基于Qwen2.5-7B镜像的结构化输出实践 在大语言模型&#xff08;LLM&#xff09;快速发展的今天&#xff0c;如何高效部署并利用先进模型进行长文本生成与结构化输出已成为开发者关注的核心问题。阿里云开源的 Qwen2.5-7B-Instruct 模型凭借其强…

作者头像 李华