[笔记]字符串哈希

定义

把一个字符串映射到一个整数的函数称作哈希函数，映射到的这个整数就是这个字符串的哈希值。

需要注意的一点是，哈希是将大空间上的东西（字符串有无穷多个）映射到了小空间（一定范围内的整数），所以必定会存在冲突，即若干个不同的字符串映射到了相同的哈希值，我们将这种冲突称作“哈希碰撞”。也就是说，不同哈希值的两个字符串一定不同，但相同哈希值的两个字符串也可能不同。

不过在大部分情况下，哈希碰撞发生概率很小。所以我们可以放心地用哈希来表示一个唯一的字符串，进而可以通过哈希值来比较两个字符串是否相等（这也是哈希最重要的性质）。

减少哈希碰撞概率的方法后面会提到。

多项式哈希函数

哈希函数有很多种，比较常用的是多项式类型（下面默认字符串下标从\(1\)开始）：
\(f(s)=\sum\limits_{i=1}^{|s|}idx(s[i])*b^{n-i}\mod P\)
其中的\(idx(c)\)表示的是\(c\)这个字符的顺序，比如\(idx('a')=0,idx('z')=25\)；
\(b\)是任意整数（一般取\(131,13331\)），而\(P\)是一个大素数（表示值域）。

子串哈希值快速计算

Libre OJ #103.子串查找

给定\(2\)个字符串\(A,B\)，求\(B\)在\(A\)中的出现次数。
\(1\le |A|,|B|\le 10^6\)。

我们知道哈希值可以用于比较字符串是否相等，然而在这道题中如果我们暴力的计算\(A\)每个长度为\(|B|\)的子串哈希值，复杂度就是\(O(n^2)\)，完全就是暴力嘛。

实际上，在我们计算\(A\)的哈希值过程中，可以换用递推的方式，用\(d[i]\)表示\(A\)的前\(i\)位的哈希值，则有：
\(d[i]=\begin{cases} 0&i=0\\ d[i-1]\times b+idx(s[i])&i>0 \end{cases}\)
那么\(s[l\sim r]\)的哈希值就是\(d[r]-d[l-1]\times b^{r-l+1}\)，可以带入验证理解一下。

#include<bits/stdc++.h>
#define int long long
#define N 1000010
#define B 131
#define P 1000000007
using namespace std;
string a,b;
int n,m,d[N],powb[N],ans,fb;
int f(int l,int r){//计算a[l~r]的hash值
	return ((d[r]-d[l-1]*powb[r-l+1]%P)%P+P)%P;
}
signed main(){
	cin>>a>>b;
	n=a.size(),m=b.size();
	a=' '+a,b=' '+b;
	powb[0]=1;
	for(int i=1;i<=n;i++){
		d[i]=(d[i-1]*B%P+a[i]-'a')%P;
		powb[i]=powb[i-1]*B%P;
	}
	for(int i=1;i<=m;i++){
		fb=(fb*B%P+b[i]-'a')%P;
	}//因为b不用求子串hash，所以就不开数组了
	for(int i=1;i<=n-m+1;i++){
		if(f(i,i+m-1)==fb) ans++;
	}
	cout<<ans<<"\n";
	return 0;
}

哈希碰撞

我们试着计算一下哈希碰撞的概率：
假设值域为\(P\)，有\(n\)个字符串，那么第\(i\)个字符串不碰撞的概率就是\(\frac{P-i+1}{P}\)。
相乘得到\(\prod\limits_{i=0}^{n-1}\frac{P-i}{P}\)，这是\(n\)个字符串互不碰撞的概率。

通过计算，可以发现在\(P=10^9+7,n=10^6\)时概率约是\(6*10^{-218}\)，也就是说几乎一定会发生碰撞。这个结论与生日悖论很相像（一个\(50\)人的班里，至少\(2\)人生日相同的概率大约是\(97\%\)）。

当我们把值域\(P\)调至\(10^{18}+9\)，不碰撞的概率达到了\(0.9999995\)，此时碰撞几乎不可能发生，这与上面的结果是截然不同的。然而实际应用中我们常常不使用调大值域的方法，主要是因为容易爆long long，使用不方便。

我们一般用双哈希的方法，即使用两个不同的模数，比如\(10^9+7\)和\(10^9+9\)（都是质数）。这样值域就扩大到了两个模数的乘积，效果相同。