ローリングハッシュ

ちょっと勉強したのでメモ

$B$ を定数、長さ $n$ の文字列を $s$ とすると $\displaystyle \sum_{i=0}^{n-1} s_i \times B^{n-i-1} \mod M$ で計算される値をローリングハッシュと言うらしい
$[l,r)$ での部分文字列のローリングハッシュの値は $(H_{0,r} - B^{r-l} \times H_{0,l}) \mod M$ で計算できる
また、長さ $m$ の文字列を後ろにくっつけた時のローリングハッシュの値は、 $(H_{0,n} \times B^{m} + H_{0,m}) \mod M$ で計算できる