Educational Codeforces #81 C. Obtain The String
AGCで見たことがある
AGC036 B - Do Not Duplicate (700) とほぼ同じ
Sにおいて各文字の出現位置を文字毎に配列に入れておく
Tを頭から見ていって、Sでのindexも記録しておく
次の移動位置は該当の文字の配列を現在のindexを使って二分探索すれば分かる
後ろにその文字が存在しない場合、カウントを増やして最初の出現位置に移動する
その文字がSに存在しない場合は作れないと言うことなので-1
カウントの数が答え
Tの文字毎にSの配列を二分探索するので$ O(|T| \log |S|)
問題: https://codeforces.com/contest/1295/problem/C
#educational-codeforces-81 #codeforces