[AtCoder] ABC 138 E – Strings of Impurity

問題

方針

シミュレーション

\( t \) に含まれる文字が \( s \) に存在しなければ、条件を満たす整数は存在しません。そうではないとき、\( t \) の \( i \) 文字目 \( t_i \) について、\( s’ \) の先頭から調べていき、\( t_i \) に一致する文字の箇所を見つけます。次に、\( t_{i + 1} \) についてその一致した箇所以降の文字列から \( t_{i + 1} \) を見つけます。このようにしていけば、条件を満たす \( s’ \) の最小の部分文字列の長さが分かります。

二分探索

ある文字 \( i \ (1 \leq i \leq 26)\) が \( s \) のどの位置に存在するかというリストが昇順に整列されたものを \( k(i, j) \) とします。このとき、\( k(i, j) \) は文字 \( i \) が \( s \) の \( j \) 番目に現れるときの \( s \) の添え字となります。

まず初めに、\( s \) を必要な回数連結するイメージで考えます。整数 \( t \ (1 \leq t \leq |s|) \) の初期値を \( 1 \) とします。\( t \) の先頭の文字から調べていき、\( t \leq k(t_i, j) \) を満たす最小の \( j \) が存在するとき、新たに \( s \) を連結する必要がありません。そうではないとき、新たに \( s \) を連結させる必要があります。連結させる必要がないとき、\( t = k(t_i, j) + 1 \) と更新し、そうでなければ、\( t = 1 \) と更新します。

連結させる必要がないとき、新たに増える文字の長さは、\( k(t_i, j) – t + 1\) となり、そうではないとき、\( t \) 以降の文字列分の長さ \( |s| – t + 1\) と \( s \) を先頭から調べた時に新たに増える文字列の長さ \( k(t_i, 1) \) を加算したものとなります。

コード