- 小さい方から順番に考える
- tが1文字の時iはsの中の最初の出現である
- 出現しない時は-1
- tが2文字の時
- 最初の出現以降の最初の出現
- 素朴には10^5のオーダーで「x以降の最初の出現」を見つけられる
- 素朴な方法だと10^10になるからダメ
- たとえば26×10^5のテーブルに「次の出現」を前計算しておけば定数オーダーになる
- この前処理は
- 文字列sの後ろから1文字ずつ見ていく
- -1を書いていく
- 文字が見つかれば0を書き、以降はインクリメントしていく
- また見つかったら0にする
- 文字列の最初まで来たら、-1でないなら、末尾から表が-1である間インクリメントしながら埋めていく
- これで文字あたり最悪2周で表が埋まる
- 文字列sの後ろから1文字ずつ見ていく
- 文字cのi+1番目を見れば「i以降の次のcの出現までの文字数」が定数オーダーでわかる
- Tの各文字についてこの値を足し合わせればOK
- tが1文字の時iはsの中の最初の出現である
- 公式解説OK
