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

f:id:peroon:20210306102041p:plain

Quiz

Submission

衝突した状況

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

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

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

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

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

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

  • ハッシュで衝突を発見したあと、実際に部分文字列どうしの比較で追加チェックを行う
  • これでロリハを１つに抑えつつ、衝突も回避できる
  • これで通したのが上記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 z algorithm