安全で爆速なRollingHashの話 - Qiita要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
