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

Quiz

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

1. ローリングハッシュ（ロリハ）

• この記事に書いた
• http://perogram.hateblo.jp/entry/2019/09/16/103911

2. 接尾辞配列

• 蟻本読んだけれど、分からない。使い方のみ理解
• 共通文字列の長さをlcpとして受け取る
• これは重なっている可能性があるので、(i, j)の差を考慮する
• 提出 https://atcoder.jp/contests/abc141/submissions/7556684

3. Z-algorithm

• snukeさんの記事も読む
• Suffix Arrayと同じくlcp（共通な長さ）が取れる
• Suffix Arrayのときと同じく、ababaのように重なってしまう場合はlcpが削られる場合がある
• 提出 https://atcoder.jp/contests/abc141/submissions/7557143
• sを削りながら何度もZ-algorithmを適用する、その発想はなかった

好きな順番

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

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