shining segtree

競技プログラミングとかについて書きます。

AOJ1316/The Sorcerer's Donut

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316

 

ドーナツに文字が刻み込まれているので、その中から複数回出現する部分文字列の中で最大の長さのものを出力する問題です。

 

入力は長方形に並べられた文字列ですが、端に行くと反対の端から出てくる仕様になっています。(ドーナツに刻み込まれているのを想像すればわかる)

 

長方形全ての文字をそれぞれ始点にした時、それぞれ8方向に探索して部分文字列を得る度にsetに突っ込んで既出だったら答えを更新します。

 

AOJ1316