ABC138E

https://gyazo.com/5f6618bde9fcd97d22a92131ae77a4f2

tが1文字の時iはsの中の最初の出現である

出現しない時は-1

tが2文字の時

最初の出現以降の最初の出現

素朴には10^5のオーダーで「x以降の最初の出現」を見つけられる

素朴な方法だと10^10になるからダメ

たとえば26×10^5のテーブルに「次の出現」を前計算しておけば定数オーダーになる

この前処理は

文字列sの後ろから1文字ずつ見ていく

-1を書いていく

文字が見つかれば0を書き、以降はインクリメントしていく

また見つかったら0にする

文字列の最初まで来たら、-1でないなら、末尾から表が-1である間インクリメントしながら埋めていく

これで文字あたり最悪2周で表が埋まる

文字cのi+1番目を見れば「i以降の次のcの出現までの文字数」が定数オーダーでわかる

Tの各文字についてこの値を足し合わせればOK