字符串hash

字符串hash是一种高效查询类似子串判重的问题的东西。

当每次我们想比较两个字符串子串是否相同时，一般情况下，要暴力匹配，时间复杂度最坏 $O(n)$。

这时，字符串hash就有作用了。 字符串hash的原理就是给每一个串赋予一个哈希值，同过比较哈希值，就可以实现 $O(1)$ 对比。 现在的问题就是：怎么实现这个哈希值？

设有一个进制 $B$，则一个字符串 $s$ 的哈希值为：

其实就是一个 $B$ 进制的位权展开。 $B$ 通常取 $131$ 或 $13331$。

但这时有一个问题：按这样计算，不是很容易溢出吗？

确实是，通常来说，我们为了避免溢出，会使用取模。 但在字符串哈希中，根据前人经验取模的时间慢和哈希冲突的分析，我们不是用取模来，而是将 hash 的值设置为

unsigned long long

现在这一个 $\text{hash}$ 数组的求法已经推出来了，预处理的时间复杂度是 $O(n)$，所以我们查询区间 hash 需要使用 $O(1)$ 的复杂度。

设区间左为 $l$，右为 $r$，$h_i$ 表示从 $1$ 到 $i$ 的串的哈希值，则 $l$ 到 $r$ 的串的哈希值为：

这个式子是如何推出来的呢？

用类似前缀和的思想，使用 $10$ 进制类比一下。有一个串 $12345$，则 $h$ 数组为 ${1,12,123,1234,12345}$，如果我们要求 $2$ 到 $4$ 之间的哈希值，手推一下，发现是 $234=1234-1\times 1000$。再举个例子，求 $3$ 到 $4$，发现答案是 $34=1234-12\times 100$。 推出来是右端点减去左端点，但是左端点要乘上两个点相差的距离来补全。

还有一些技巧，就是使用多个哈希，比如双哈希和三哈希以加快查询效率和减少冲突。 比如双哈希时就是都要比较。

注意点 1.计算 $B$ 的任意次方要使用 $O(n)$ 的预处理和 $O(1)$ 查询，如果用快速幂的 $O(\log n)$ 的话总复杂度是 $O(n\log n)$。 2.使用多哈希的时要注意，每一个哈希的 $B$ 值要不一样，且一定要是质数。

code

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B=13331;
const int N=1e6+10;
char s[N];
ull h[N];
ull p[N];
int n;
void get(){
	p[0]=1;
	for(int i=1;i<=n;i++){
		p[i]=p[i-1]*B;	
	}
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*B+(s[i]-'a'+1);
	}
}
bool ask(int l1,int r1,int l2,int r2){
	ull a=h[r1]-h[l1-1]*p[r1-l1+1];
	ull b=h[r2]-h[l2-1]*p[r2-l2+1];
	//cout<<"ask:"<<a<<' '<<b<<'\n';
	return a==b;
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	get();
	int m;
	cin>>m;
	while(m--){
		int l1,r1,l2,r2;
		cin>>l1>>r1>>l2>>r2;
		if(ask(l1,r1,l2,r2)){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}
	return 0;
}