在 CSP-S 信息学奥赛的最后一个月考前冲刺阶段，字符串哈希是一个重要的考点。今天我们就来详细讲讲字符串哈希的实战技巧，重点聚焦于双哈希及相关优化方法。
一、字符串哈希的基本概念
字符串哈希是将字符串转化为一个固定大小的整数值，以便于进行快速的比较和查找操作。通过哈希函数，相同的字符串能够得到相同的哈希值。
二、双哈希的优势
双哈希采用两个不同的模数和基数，大大降低了哈希冲突的概率。常见的模数可以选择 1000000007 和 1000000009 等较大的质数，基数可以选择 131 或 13331 等。
三、预处理前缀哈希数组和幂次数组
为了快速计算任意子串的哈希值，我们需要预处理前缀哈希数组和幂次数组。
前缀哈希数组 h[i] 表示字符串前 i 个字符的哈希值。
幂次数组 p[i] 表示基数的 i 次幂对模数取余的结果。
通过这两个数组，可以在常数时间内计算出任意子串的哈希值。
四、快速计算子串哈希值的公式
假设要计算字符串 s 中从第 l 个字符到第 r 个字符的子串哈希值，公式为：
hash(s[l...r]) = (h[r] - h[l-1] * p[r-l+1] % mod + mod) % mod
五、代码模板的封装
为了方便使用，我们可以将字符串哈希的相关操作封装成代码模板。
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
// 初始化前缀哈希数组和幂次数组
void init() {
p[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i-1] * P + str[i];
p[i] = p[i-1] * P;
}
}
// 获取子串 [l, r] 的哈希值
ULL get(int l, int r) {
return h[r] - h[l-1] * p[r-l+1];
}
六、实战应用中的注意事项
在实际应用中，要注意处理边界情况，比如空字符串或单个字符的子串。同时，要选择合适的模数和基数，以平衡计算的效率和冲突的概率。
总之，在最后的冲刺阶段，熟练掌握字符串哈希的实战技巧，包括双哈希、前缀哈希数组和幂次数组的使用以及代码模板的封装，对于提高解题速度和准确性至关重要。希望同学们通过不断的练习和总结，能够在 CSP-S 考试中取得优异的成绩！
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
