字符串Hash
字符串Hash原理,将字符串映射成一个值,是一个单向加密的过程。比较简单和常用的是进制哈希,我们把字符串看成是p进制数,然后使用unsigned long long的自然溢出(相当于是对$2^{64}$取模)是对$2^64$取模,如果两个字符串的hash值相同,则可以认为两个字符串相同。
单个字符串的Hash值
要求长度为$len$的字符串$str$的Hash值
先预处理出一个$pwd[]$数组,$pwd[i]$表示$p^i$。
Hash[]表示字符串的哈希值(p进制取模值)。显然有
$$Hash[i]=(Hash[i-1]*p+str[i]$$
这样我们可以On求出$str$的哈希值。
子串的Hash值
在上面我们已经求得Hash[i]表示字符串abcbc
的前缀子串的哈希值。假如现在我们要求区间bc
这个子串的哈希值该怎么做呢?
先来看Hash[i]:
$Hash[1] : p^1 * str[1]$
$Hash[2] : p^2 * str[1] + p^1 * str[2]$
$Hash[3] : p^3 * str[1] + p^2 * str[2] + p^1 * str[3]$
$Hash[4] : p^4 * str[1] + p^3 * str[2] + p^2 * str[3] + p^1 * str[4]$
$Hash[5] : p^5 * str[1] + p^4 * str[2] + p^3 * str[3] + p^2 * str[4] + p^1 * str[5]$
现在要求子串bc的哈希,也就是l=2,r=3的Hash值,就是
$Hash[r]-Hash[l-1]*pwd[r-l+1]$
可以发现,$Hash[5]-Hash[3]pwd[2]$结果和$Hash[3]-Hash[1]pwd[2]$一样。也论证了一样的字符串Hash值一样的结论。
AC代码:
1 | unsigned long long pwd[100010], Hash[100010]; |