算法简介
字符串哈希是将字符串映射为数字的算法，它通常用来解决快速判断两个字符串是否相等的问题。
时间复杂度
\(O(n + m)\)
实现原理
1. 构造原理
字符串哈希运用了进制的思想，将字符串变为 p 进制的数字。
如：""
可以映射为：\((X_1 * P^{n-1} + X_2 * P^{n-2} + \cdots + X^{n-1} + X_n * P^{0}) \mod Q\)
该过程中需要注意的点是：
- 字符不能映射为 0 ，否则会出现 A，AA，AAA 字符串全部映射为 0 的情况。
- P 一般取值 131 或 13331 时冲突概率最小。
- Q 一般取值 \(2^{64}\)，等同于 unsigned long long 的数据范围，可以利用 C++ 的溢出机制自动取模。
2. 区间哈希值
这里用数组 h[i] 表示当前字符串前 i 个字符组成的字符串的哈希值
例如："ABCDEFGHIJK"
h[1] = "A" 的哈希值
h[2] = "AB" 的哈希值
h[3] = "ABC" 的哈希值
...
h[11] = "ABCDEFGHIJK" 的哈希值
那么如何求得 [l,r] 区间内的哈希值呢？
给出公式：\(h[l,r] = h[r] - h[l-1] * p^{r-l+1}\)
假设有字符串 ABCD：
则有：
\(h[1] = A * p^0\)
\(h[2] = A * p^1 + B * p^0\)
\(h[3] = A * p^2 + B * p^1 + C * p^0\)
\(h[4] = A * p^3 + B * p^2 + C * p^1 + D * p^0\)若要求 BC 的哈希值，那么根据公式则有：
\(h[2,3] = h[3] - h[1] * p^2\)
则有
\(h[3] - h[1] * p^2 = (A * p^2 + B * p^1 + C * p^0) - (A * p^0) * p^2 = B * p^1 + C * p^0 = "BC"\)
或者可以通俗理解，copy 一个大佬的解释：
算法实例
1. 题目描述
https://www.acwing.com/problem/content/description/843/
2. AC代码
#include <bits/stdc++.h>
typedef unsigned long long ULL;
const int N = 100010, P = 131; // P = 13331
int n,m;
char str[N];
ULL h[N], p[N];
ULL get(int l,int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
std::cin >> n >> m;
std::cin >> 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;
std::cin >> l1 >> r1 >> l2 >> r2;
if(get(l1,r1) == get(l2,r2)) puts("Yes");
else puts("No");
}
return 0;
}