perogram

ローリングハッシュ

ローリングハッシュ2

前回の説明 http://perogram.hateblo.jp/entry/rolling_hash これでは通らない問題もあった(下記) そこで、蟻本にならってh=264バージョンで書き直すとAC. 先人の知恵 Code // ローリングハッシュ // h = 2^64にすることでmod不要 using ull = unsigned lo…

ローリングハッシュにより文字列検索をO(m*n) => O(m+n)に高速化

参考 蟻本第二版 p332 プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: マイナビ発売日: 2012/01/28メディア: 単行本(ソフトカバー)…