読者です 読者をやめる 読者になる 読者になる

ローリングハッシュ

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

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で計算できる

ハッシュ値の衝突についてはハッシュを衝突させる話

ソースコード

衝突を起こらないようにするには、複数のmodで計算するのがいいらしい

ローリングハッシュ

例題

AOJ2444
Codeforces Round0291 Div2 C

参考にしたサイト

http://d.hatena.ne.jp/say_hello_to_okaoka/20140204/1391484891

http://algoogle.hadrori.jp/algorithm/rolling-hash.html

http://kmjp.hatenablog.jp/entry/2015/02/15/0900

あり本第二版には載ってるらしい。購入しないとなあ