問題

解法

sの右側から貪欲にtの要素を拾っていったときに，t[i:|t|]が作れる最初のインデックスxをr[i]と定義します．言い換えると，s[x:|s|]からt[i:|t|]を作ることができるような最も右側のxをr[i]と定義します．各i(1<= i <= |t|)についてr[i]を事前に計算しておきます．
各j(1<= j <= |s|)について，jから最大で何文字切り取れるか，を全探索します．つまり，s[j:y)を切り取ったあとの文字列からtを作ることができるような最も右側のyを探します．ここで，左側から貪欲にtの要素を拾っていったときに，0~j-1の間でt[next-1]文字まで回収できていたとします．このとき，次に必要となる要素はt[next]です．r[i]の定義からyを最大化するためには，y=r[next]とすれば良いことが分かります．よって，jから最大で何文字切り取れるかの答えはr[next]-jとなります．ただし，そもそもtを作れないケースや，jまででtの要素をすべて回収できるケースがあるので，別途場合分けが必要です．

何を固定して全探索すれば良いか分からなかった．間に合うはずのないDFSを書いてしまったのも反省点．