ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC138 E - Strings of Impurity

問題
提出コード

解法

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

感想

それなりにスッキリとした実装ができたので個人的に満足です。