perogram

ローリングハッシュの衝突回避と定数倍高速化

Quiz

Submission

https://atcoder.jp/contests/abc141/submissions/7553482

衝突した状況

  • 途中のデータでWA. 1つのロリハでは衝突してしまったのだろう

衝突回避のために取れる手段1

  • ロリハを複数本用意する
    • 計算量が本数倍になる。今回の問題では1本で1100msほどかかっているので2本に増やすとTLEする

ロリハを複数本用意するときの知見

  • modを変えた2本を用意したがWAが取れなかった
  • 他のパラメータとして、baseというのがあり、そちらも変えたらWAは消えた
  • しかし本数を増やしたのでTLEは残る

衝突回避のために取れる手段2

  • ハッシュで衝突を発見したあと、実際に部分文字列どうしの比較で追加チェックを行う
  • これでロリハを1つに抑えつつ、衝突も回避できる
  • これで通したのが上記Submissionである
ll hash0 = rh.get(i, i+L);
ll hash1 = rh.get(j, j+L);
if(hash0==hash1 && s.substr(i, L)==s.substr(j, L)){
  // ...
}

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

別解