字符串哈希

BKDRHash算法

字符串哈希，就是一种可以理解为将字符映射到一个整数的方法，即字符串会对应一个整数值。字符串哈希算法很多，在算法竞赛中，$BKDRHash$是一种很好的哈希算法，冲突的概率几乎为$0$，感谢前人的研究。
假设字符串为$a$，则它对应的哈希值就为：
$BKDRhash(a)=\sum _{i=1}^{a.size()}a[i-1]\times P^{a.size()-i}\mathrm{\%}Q$
怎么去理解这个哈希函数呢？可以发现，这其实是把字符串转换为了一个$P$进制的数的过程（所以也叫“进制哈希”），这样做可能会导致数字过大，导致溢出，所以转换完后要再对$Q$进行取余。
如何去计算哈希？可以采用递推的方法，采用一个数组记录字符串前i位的哈希值，例如,$S=abcdefg$,它的前缀有$a,ab,abc,abcd,\dots$。计算过程如下。

1. 计算前缀a的哈希值,得 $H(a)$ ,计算时间为$O(1)$。
2. 计算前缀ab的哈希值。 $H(ab)=H(a)\times P+H(b)$ ,计算时间为 $O(1)$ 。
3. 计算前缀abc的哈希值。$H(abc)=H(ab)\times P+H(c)$ ,计算时间为 $O(1)$,等等……

只需一个$for$循环遍历$S$,就能在 $O(n)$的时间内预处理所有前缀的哈希值。

计算出$S$的所有前缀的哈希值后,能以 $O(1)$的复杂度查询它的任意子串的哈希值,如 $H(de)=H(abcde)-H(abc)\times P^2$求区间$[L,R]$的哈希值的代码可以这样写(其中 $P[i]$表示$P$的$i$次方):

ull get_hash(ull L,ull R)  
{  
	return H[R]-H[L-1]*P[R-L+1];  
}  

在这里$ull$表示$unsignedlonglong$，这样在计算溢出的时候，也不会变为负数。

哈希碰撞

两个字符串哈希值一样的情况（冲突）就叫哈希碰撞，为了有效避免哈希碰撞，进制$P$常用的数值有$31$,$131$,$1313$,$13131$,$131313$等。
万一出现哈希碰撞过不了测试点，还可以用双哈希，双哈希指的是对字符串用两队不同的$P$和$Q$得到不同的哈希值。只有这两个哈希值都对应相同，才判定两个字符串相同。
7861-兔子与兔子
7192-Oulipo