在信息学奥赛CSP - J的备考冲刺阶段（第5个月），算法综合中的字符串哈希是一个重要的考点。
一、双哈希的概念及意义
字符串哈希是将字符串映射为一个固定大小的整数。而双哈希就是同时使用两个不同的基数和模数来进行哈希操作。比如常见的第一种哈希方式可能是基数为31，模数为1e9 + 7；第二种可以是基数为131，模数为1e9 + 9。这样做的好处是能够极大地降低碰撞概率。当我们对一个字符串进行哈希时，如果只采用一种哈希方式，可能会存在不同字符串得到相同哈希值的情况（即碰撞）。而双哈希通过两种不同的计算方式，只有当两种哈希结果都相同时，我们才认为这两个字符串是相同的。这就如同给字符串从两个不同的角度做了标记，只有两个标记都一样的时候才判定为同一个。
二、预处理前缀哈希数组
预处理前缀哈希数组是处理字符串哈希问题的一个有效技巧。我们定义一个数组hash[i]表示字符串前i个字符的哈希值。对于单哈希来说，假设字符串为s，基数为base，模数为mod，那么hash[i]=(hash[i - 1]*base + s[i])%mod。对于双哈希，我们有两个这样的数组，分别按照两种不同的基数和模数计算。学习这个知识点的时候，要理解每一个字符是如何逐步参与到哈希值计算中的。可以通过多做一些简单的示例字符串的计算练习来掌握。
三、快速计算子串哈希值的技巧
计算子串哈希值时，我们可以利用前缀哈希数组快速得到。对于单哈希，如果我们要求s[l…r]的哈希值，设p为base的幂次方，p[i]=(base^i)%mod，那么子串的哈希值hash[l…r]=(hash[r] - hash[l - 1]*p[r - l + 1] + mod)%mod。双哈希同理，分别按照两种哈希方式计算子串哈希值并且都要满足相等情况才确定子串相同。这部分内容需要理解公式的推导过程，多做一些有针对性的题目，熟练掌握公式的运用。
四、代码模板
以下是双哈希相关的简单代码模板：
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int base1 = 31;
const int base2 = 131;
ll p1[100005], p2[100005];
ll hash1[100005], hash2[100005];
void init(string s) {
int len = s.length();
p1[0] = 1;
p2[0] = 1;
for (int i = 1; i <= len; i++) {
p1[i] = (p1[i - 1] * base1) % mod1;
p2[i] = (p2[i - 1] * base2) % mod2;
}
hash1[0] = 0;
hash2[0] = 0;
for (int i = 1; i <= len; i++) {
hash1[i] = (hash1[i - 1] * base1 + s[i - 1]) % mod1;
hash2[i] = (hash2[i - 1] * base2 + s[i - 1]) % mod2;
}
}
pair<ll, ll> getHash(int l, int r) {
ll h1 = (hash1[r] - hash1[l - 1] * p1[r - l + 1] + mod1) % mod1;
ll h2 = (hash2[r] - hash2[l - 1] * p2[r - l + 1] + mod2) % mod2;
return make_pair(h1, h2);
}
int main() {
string s;
cin >> s;
init(s);
// 之后可以进行子串哈希相关的操作
return 0;
}
在备考过程中，要深入理解这些知识点之间的联系，并且通过大量的练习题来巩固所学内容，这样才能在考试中熟练运用字符串哈希相关的算法。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
