perogram

同じ問題をZ-Algorithm, Suffix Array, Rolling Hashで解く

Quiz

  • https://atcoder.jp/contests/abc141/tasks/abc141_e
  • 3パターンで解いた。とはいえ完全に「けんちょん」さんの記事に依存している
  • 解いた順に書く
  • あとから検索する用に書いている。1度使ったコードは安心感があるため

1. ローリングハッシュ(ロリハ)

2. 接尾辞配列

f:id:peroon:20190916153328p:plain

3. Z-algorithm

好きな順番

  • Z-algo(短いしハッシュ衝突もしないため)
  • ロリハ(理解できるため)
  • Suffix Array(理解できないため)

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

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