题目描述
链接在此
AcWing 841
字符串前缀哈希法：
定义 ${h_n}$ 为字符串 $str$ 的前缀哈希值，其中 $h_i$ 为前 $i$ 位的哈希值。
那么该如何定义某一前缀字符串的哈希值？
假定字符串为 $s_1s_2\cdots s_n$ ，那么字符串的 $h_i$ 对应的前缀为 $s_1s_2\cdots s_i$ ，定义字符串的数值为 $val$ ，我们把字符串转换成一个 $p$ 进制的数。那么，字符串 $s_1s_2\cdots s_i$ 对应的值为 $val=s_1\times p^{i-1}+s_2\times p^{i-2}+\cdots+s_i\times p^0$ ，定义哈希函数为 $h(x)=x\mod Q$ ，则最后得到的 $h(val)$ 就是 $h_i$ 的值。显然，$h(x)\in (0,Q)$
这里需要注意两点。首先，对于一个字符我们不能将其换算为 $0$ 。假如将 $A$ 映射成 $0$ ，那么 $AA$ 也就是 $0$ ，将会无法区分，这里我们采用其 ASCII 码去进行换算；第二，这里我们假设我们的哈希方法是不存在冲突的。一般经验值为 $p=131/13331$ 、 $Q=2^{64}$ 。
以上就是定义的字符串哈希方式。我们通过这样的定义方式就可以得到所有子串的哈希值。假定给出区间 $[l,r]$ ，那么根据前缀和的思想，我们需要的是 $h_r,h_{l-1}$ 这两个数。对于字符串 $str$ 内部而言，由于我们定义了要将字符串转化为一个 $k$ 进制的数，则从 $s_1$ 到 $s_n$ 为字符串的高位到低位。那么，我们再分别单独看两个子串，这两个前缀子串当中，$s_1$ 是高位，而 $s_{l-1},s_r$ 是低位。但两个子串相对而言，虽然他们的高位相同，但是，其实在数值上，以 $s_1$ 为例，这里我们用前缀字符串哈希值来代表某一个前缀子串，那么 $h_r$ 的 $s_1$ 对应的值应当是 $s_1\times p^{r-1}$ ，而相对应的 $h_{l-1}$ 中是 $s_1\times p^{l-2}$ 。可以看到，其实两个字符串的哈希值差了 $p^{r-1-(l-2)}=p^{r-l+1}$ 倍的。那么，如果想要进行 ”同等“ 的运算，我们就应当将小的哈希值字符串按位扩大相差的倍数才能进行运算。所以，我们就得到了计算区间 $[l,r]$ 的子串哈希值的公式为：$h_{l,r}=h_r-h_l\times p^{r-l+1}(l\leq r)$ 。这里需要说明的一点是，我们定义的哈希函数是 $h(x)=x\mod Q$ ，这里并不是不进行取模运算了，我们用 unsigned long long 存储所有的哈希值，unsigned long long 的阈值是 $2^{64}$ ，所以如果溢出了范围，也就相当于是对 $2^{64}$ 进行取模运算了。
仿照我们上面扩大倍数的思想，我们得到哈希值的方式也很简单。相邻两位上相差的倍数就是 $p$ ，那么就有如下公式成立：$h_i=h_{i-1}\times p+s_i$ 。
typedef unsigned long long ULL;
const int P = 131;
char str[N];
ULL h[N], p[N]; // h stores hash values, p stores the pow of P
预处理
p[0] = 1;
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
}
获取某一区间内子串的哈希值
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
判断两个子串是否完全相同：如果两个子串的哈希值完全相同，那么就判定两者完全相同。因为对于任意的每一个不同的字符串而言，其哈希值是唯一的。
bool judge(int l1, int r1, int l2, int r2) {
if (get(l1, r1) == get(l2, r2)) return true;
else return false;
}
代码
C++
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
ULL h[N], p[N];
char str[N];
inline ULL gethash(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
while (m--) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if (gethash(l1, r1) == gethash(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Python
def gethash(l, r):
return (h[r] - h[l - 1] * p[r - l + 1]) % (1 << 64)
if __name__ == '__main__':
n, m = map(int, input().split())
P = 131
s = ' ' + input()
h = [0] * len(s)
p = [0] * len(s)
p[0] = 1
for i in range(1, n + 1):
h[i] = (h[i - 1] * P + ord(s[i])) % (1 << 64)
p[i] = (p[i - 1] * P) % (1 << 64)
for _ in range(m):
l1, r1, l2, r2 = map(int, input().split())
if gethash(l1, r1) == gethash(l2, r2):
print("Yes")
else:
print("No")
