『算法-ACM 竞赛-算法-Hash 算法』信息竞赛进阶指南-字符串哈希

字符串 hash 主要应用在：

寻找长度为 n 的主串 S 中的匹配串 T（长度为 m）出现的位置或次数的问题属于字符串匹配问题。
类似的还有 KMP，我也有讲解。

原理：

1. 将字符串中的每一个字母都看做是一个数字（例：从 a-z，视为 1-26）；

2. 选取两个合适的互质常数 b 和 h，其中 h 要尽可能的大一点，为了降低冲突的概率。

3. 定义哈希函数，$H(C)=[ c_1b^{(m-1)} + c_2b^{(m-2)} + . . . + c_m*b^0 ] mod \ h$

   1. C 代表一个字符串，用 C=c1 c2 c3 c4..cm;表示该字符串，其中 ci 表示从前向后数的第 i 个字符；
   2. 方括号[ ]内的表达式：c1b^(m-1) + c2b^(m-2) + . . . + c0*b^0 意为将字符串 C 当做 b 进制数 来处理，b 是基数；
   3. 关于对 h 取模，若 b，h 有公因子，那么不同的字符串取余之后的结果发生冲突的几率将大大大增加（ 冲突：不同的字符串但 会有相同的 hash 值）

4. 计算上一步$H(C)$的过程是递归实现的：H(C,k)为前 k 个字符构成的字符串的哈希值，（若不考虑取模）：

H(C,k+1)= H( C , k ) * b+c( k+1 );

5. 判断 主串上 长度为 n 的任意子串 C ‘=c(k+1) c(k+2) c(k+3) . . . c(k+n) 与 待匹配串 S=s1 s2 s3. . .sn 的哈希值是否相等,则：

H(C ’)= H( C , k+n ) - H(C, k ) * b^n;

实现：

//模板是李煜东的信息进阶指南
char s[1000010];
unsigned long long f[1000010], p[1000010];
int n, q;
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	cin >> q;
	p[0] = 1; // 131^0
	for (int i = 1; i <= n; i++) {
		f[i] = f[i-1] * 131 + (s[i]-'a'+1); // hash of 1~i
		p[i] = p[i-1] * 131; // 131^i
	}
	for (int i = 1; i <= q; i++) {
		int l1, r1, l2, r2;
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		if (f[r1] - f[l1-1] * p[r1-l1+1] == // hash of l1~r1
			f[r2] - f[l2-1] * p[r2-l2+1]) { // hash of l2~r2
			puts("Yes");
		} else {
			puts("No");
		}
	}
}