信奥赛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;}