滚动哈希&Rabin-Karp算法

滚动哈希是一种快速计算字符串哈希值的方法。它利用字符串前后子串的关系，只需要 O(1) 的时间就可以计算新的哈希值。

字符串的Hash code

b 是选择的基数，来作为各个位数上的区分，一般b取131或1331等质数

p是用来规避哈希冲突的,是大的素数

初始子字符串的哈希值

对于长度为 m 的子字符串 S[0..m-1]，其哈希值计算如下：

$$H(S[0..m-1]) = S[0] \times b^{m-1} + S[1] \times b^{m-2} + \ldots + S[m-1] \times b^0 \% p$$

滚动更新哈希值

假设已经计算了子字符串 s[r] 的哈希值 H(s[r])，现在需要计算子字符串 s[r+1] 的哈希值。可以使用以下公式滚动更新哈希值：

$$H(s[r+1]) = H(s[r]) \times b + s[r+1] \% p$$

前缀和

当我们需要计算子串 s[l, r] 的哈希值，只需要利用前缀和思想(注：hashCode之间相减，得到的hashCode有可能是负数):

$$H(s[l, r]) = (H(s[r]) - H(s[l-1])\times pow(b,r-l+1) \% p + p )\%p$$