引言
字符串哈希是用来将字符串映射到一个固定大小的哈希值的算法，其可以用来快速比较字符串是否相等。
原理
对于如 \(s_1 s_2 \cdots s_n\) 的字符串，采用二进制的思想，将其视为 \(P\) 进制，该字符串的值即为将其转化为十进制的值。
则可以将其表示为：
\[(s_1 \times P^{n-1} + s_2 \times P^{n-2} + \cdots s_n \times P^0) % Q
\]
为防止数溢出，需要定义一个模 \(Q\)
用 \(h[i]\) 数组表示子串 \(s_1 s_2 \cdots s_i\) 的哈希值。
如果需要其 \([l,r]\) 子串的哈希值，则有下列公式：
\[h[l,r] = h[r] - h[l - 1] \times P^{r - l + 1}
\]
证明：
\(h[r] = s_r \times P^0 + s_{r - 1} \times p^1 + \cdots + s_l \times P^{r - l} + \cdots + s_0 \times P^r\)
\(h[l] = s_{l-1} \times P^0 + \cdots + s_0 \times P^{l - 1}\)
\(h[l,r] = s_r \times P^0 + s_{r-1} \times P^1 + \cdots + s_l \times P^{r - l}\)
所以有 \(h[l,r] = h[r] - h[l - 1] \times P^{r - l + 1}\)
注意点：
-
字符不可映射为 \(0\)，否则会出现多个子串同时为 \(0\) 的情况。
-
\(P\) 设置为 \(131\) 或 \(13331\) 时产生冲突的概率较小。
-
\(Q\) 设置为 \(2^{64}\) 时产生冲突概率小，这里可以用 \(unsigned \ long \ long\)，溢出自动取模。
代码
#include <bits/stdc++.h>
#define P 131
#define N 2000
#define ULL unsigned long long
char str[N];
ULL h[N], p[N];
// 查看当前字符串 [l,r] 的哈希值
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
// 求当前字符串 s 的哈希值
void hashchar(char s[]) {
for (int i = 1 ; i <= strlen(s) ; i ++ ) {
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i - 1];
}
}