# E - Who Says a Pun? (opens new window)
# 概要
- 長さの文字列がある
- の連続する部分文字列として最長のものを求めよ
# 思考
- std::mapにいれて愚直にやればO(N^2 logN)になる
- 実装
- 通らない
- なぜ？
ここで30分終了
- 質問する
- std::mapの中のstd::stringで文字列の比較にO(N)かかるのでこうなる (opens new window)
- 別の実装を考える
- stringでなければ良いのでは?
- 数字列にすると簡単にオーバーフローする
- お手上げ
解説を見る
- Z-Algorithm?
- けんちょんさんの記事が良さそう (opens new window)
- 時間がかかりそうなので続きは明日
# 提出
- してません
# 気づいたこと・感想
- 文字列に関する知識が皆無だった
- これは解けない問題な気がする