AOJ-ICPC

難易度表/ほぼ周期文字列

難易度 問題名 出典 解いた人数
600 ほぼ周期文字列 (☆) 夏合宿2015:day2F 31

投票 (4)

投票するにはログインしてください.
投票者 難易度/推薦 投票理由
@square10011 1000 (☆) 考察面・実装面ともに難しい。文字の種類数を Σ として計算量 O(N + Q log N) の解法を実装したが、非常に多くのステップを利用しなければ解くことができない。自分が (最初に) AOJ に提出した解法 (https://onlinejudge.u-aizu.ac.jp/solutions/problem/2711/review/3324790/square1001/C++11) は Suffix Array を使わずローリングハッシュを使ったが、後になって Suffix Array (SA-IS) を使うとこの問題を O(N log Σ + Q)、つまりほぼ線形時間で解けることが分かった。 (2019-01-05 19:01:01)
@HIR180 550 (2017-06-15 01:38:47)
@asi1024 700 (Imported) 650 (2016-08-15 07:03:28)
@sigma425 550 (Imported) 550 (2016-08-15 07:03:28)

コメント (0)