AOJ 12/11

2014-12-11 | [Competitive programming]

2324

query が 2 文字以下の場合はどう考えても不可能である．

3 文字以上の場合は，αβ という現れがあったら α→β の辺を張るという規則で作る有向グラフを考える． ただし，複数回の現れがある場合でも 1 本の辺のみを張ることにする． 題意に合致する question string は，このグラフ上で，辺のないところのジャンプを許した Euler 路で，query string と同じたどり方をする部分を含まないものである．

• グラフが，ジャンプを許さない Euler 路を持たない場合 ジャンプを許した Euler 路のうち最小のものが答えである． この長さは query string の長さ以下であるから，query string と同じものを作ってしまっても適当に順番を変えることで別な文字列が得られる．

• グラフが，ジャンプを許さない Euler 路を持つ場合 グラフの構成時に，重複辺があった場合は，単に Euler 路を作ると query string より短くなるので答えになる． さもなくば，Euler 路が一意かどうか判定する．一意ならば，長さを query string 以下にはできない． 一方，ちょうど 1 だけ長い question string は構成可能である． 一意でなければ，query string と同じ長さかつ異なる question string が構成できる．