字符哈希算法
题目描述:给定一个长度为 n 仅由小写字母构成的字符串 S，再给定 q组查询，每次查询给定 4 个整数 l1,r1,l2,r2 你需要输出 Sl1∼r1 与 Sl2∼r2是否相同。
题目链接:http://47.121.118.174/p/80
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// N: 字符串最大长度, B: 进制数(通常选131或13331), mod: 大质数(用于防溢出和冲突)
const int N=2e5+10, B=131, mod=998244353;
ll pre[N]; // 存放字符串的前缀哈希值
ll base[N]; // 存放 B 的 i 次方，方便后续 O(1) 提取区间哈希
string s;
int n, q;
// 预处理函数：计算 base 数组和前缀哈希数组 pre
void init(){
base[0]=1; // B 的 0 次方是 1
for(int i=1; i<=n; i++){
// 递推计算 B 的 i 次方，记得取模
base[i] = (base[i-1] * B) % mod;
// 计算前缀哈希：前一个状态的值乘上进制 B，加上当前字符的 ASCII 相对值
// 这里减去 '0' 是为了把字符映射成数字，只要映射规则唯一即可
pre[i] = (pre[i-1] * B + s[i] - '0') % mod;
}
}
// 核心功能：O(1) 获取区间 [l, r] 的哈希值
ll getH(int l, int r){
// 将 pre[l-1] 乘以 B 的 (r-l+1) 次方，使其与 pre[r] 的位数对齐后相减
// 注意：因为 C++ 中负数取模还是负数，所以要加上 mod 再取模，保证结果为正
return ((pre[r] - pre[l-1] * base[r-l+1]) % mod + mod) % mod;
}
int main(){
// 优化输入输出速度
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
cin >> s;
// 关键操作：在原字符串前面垫一个空格，使其有效字符下标从 1 开始
s = " " + s;
init(); // 必须在字符串读入并处理好下标后，再进行预处理
for(int i=1; i<=q; i++){
int l1, r1, l2, r2;
// 每次必须读满 4 个变量
cin >> l1 >> r1 >> l2 >> r2;
// 比较两段区间的哈希值，如果相等则认为子串相同
if(getH(l1, r1) == getH(l2, r2)) cout << "Yes" << "\n";
else cout << "No" << "\n";
}
return 0;
}
注意点:负数取模问题（最容易全盘崩溃的坑） 在 getH 函数中，计算区间哈希的公式是基于前缀和相减的：
H(l,r)=(pre[r]−pre[l−1]×Br−l+1)(modM)在 C++ 中，如果 pre[r] 小于 pre[l-1] * base[r-l+1] 取模后的值，相减就会得到一个负数。C++ 对负数取模（比如 -5 % 3）得到的是 -2 而不是正数 1。
正确写法：必须像你代码里那样写成 ((A - B) % mod + mod) % mod，这能强制把负数“拉回”到正数范围内。
- 数据类型溢出（忘记开 long long） 在计算 base[i] 和 pre[i] 时，中间过程会发生乘法：pre[i-1] * B。 如果 pre 数组用的是普通的 32 位 int，这两个数相乘极容易超过 2×10 9 （int 的上限），导致直接溢出变成负数，彻底污染后续所有的哈希值。
防坑指南：哈希值的数组和相关计算函数，必须使用 long long（也就是你的 ll），你这点做得很好。
- 忘记对齐下标（数组越界） 就像我们之前聊过的，哈希区间查询需要用到 pre[l-1]。如果字符串从 0 开始存，当查询 l = 0 时，就会访问 pre[-1] 导致段错误或读到脏数据。
防坑指南：永远记得在输入字符串后加上 s = " " + s;，强制让有效下标从 1 开始。
- 哈希冲突（被出题人“卡”数据） 你使用的这套被称为单哈希（Single Hash）。你选了 B=131 和 mod=998244353。通常情况下这足以应付大部分题目。 但是在稍微高级的比赛中（比如 Codeforces），有些坏心眼的出题人会专门构造针对常见 mod（如 10 9 +7 或 998244353）的“碰撞数据”，导致两个不同的字符串算出完全一样的哈希值，从而输出错误的 Yes。
进阶防坑：如果你发现逻辑全对但就是过不了某些测试点（WA），说明你被卡哈希了。解决方法是换一个冷门的质数（比如 mod=109+9 或更大），或者直接写双哈希（用两组不同的 B 和 mod 分别计算，两次都相等才算相等）。自然溢出法（直接用 unsigned long long 让它自动溢出代替取模）现在非常容易被针对，不建议使用。
