ABC138 E - Strings of Impurity
解法
に含まれ、に含まれない文字が存在する場合、答えは-1になります。逆に、それ以外の場合は、必ず答えを見つけることができます。
の部分列でを作る際、お互いの先頭から順番に、一致する部分を選んでいけばよいです。
作りたい文字列はと固定されているので、の文字目がの何文字目に相当するかを調べていけば、の最後の文字と対応するの番号が答えになります。
あとは、愚直にシミュレーションをしていきます。
あらかじめ、を文字の種類ごとに分け、どの文字には何文字目が含まれるか、を調べて昇順で記録しておきます。
そして、今の何文字目に居るか、というインデックスを更新しながら(初期は0文字目、としておきます)シミュレートしていきます。
次に決めるのがの文字目のとき、よりも後で登場するの場所を、先ほどの記録を二分探索して探します。よりも後ろにが存在しない場合は、の中で一番最初に存在するの場所になります。
そして、を今探した場所に更新すればよいです。
これを繰り返すと、最終的にいる位置がわかります。
そして、肝心の答えですが、先ほど以降にが存在しなかった場合、を1周することになるので、
になります。
感想
それなりにスッキリとした実装ができたので個人的に満足です。