ABC141 E - Who Says a Pun? (500)
最大値を二分探索で求める
ローリングハッシュを使うと
$ O(1)
で文字列比較ができる
単純に同じ長さの全部分文字列を比較すると
$ O(N^2)
二分探索一回毎にこれを行うと、
$ O(N^2 \log N)
でTLE
部分文字列のハッシュと出現位置を持っておいて、len以上前で出現していたら重複していないので作れる、という風に判定を変える
一重ループなので
$ O(N \log N)
問題:
https://atcoder.jp/contests/abc141/tasks/abc141_e
提出:
https://atcoder.jp/contests/abc141/submissions/7561088
#ABC141
#500pt
#E
#ABC
#AtCoder