ローリングハッシュ(Rabin-Karp法)
#文字列
数列をハッシュで表すことで、比較を
$ O(1)
でやってしまおうというアルゴリズム
詳細はこの記事
https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
応用
累積和を使うと、部分文字列のハッシュを
$ O(1)
で取得できる
セグ木に乗せると、変更クエリを処理できる
順と逆の二通りでハッシュを取ると、回文判定ができる
ABC331 F - Palindrome Query
Hack
Rolling Hashを殺す話
■ 2014/08/20 - ハッシュを衝突させる話