以下 \(|S|=N, |T|=M\) とおきます．

\(S\) の \(l\) 文字目から \(r\) 文字目を取り出して得られる部分文字列を，\(S(l, r)\) と表します．このとき，\(S(l, r)\) の部分列に \(T\) が含まれる最小の \(r\) を \(r_{max}(l)\) とすると，

• \(r \geq r_{max}(l)\) のとき，\(S(l, r)\) は \(T\) を部分列として含む．
• \(r < r_{max}(l)\) のとき，\(S(l, r)\) は \(T\) を部分列として含まない．

これにより，答えは \(\sum_{1 \leq l \leq N}(r_{max}(l) - l)\) となります．

\(l\) を固定したときの \(r_{max}(l)\) の求め方を考えましょう．これは，\(nxt(i, c) =\)(\(S\) において，\(i\) 文字目以降で文字 \(c\) が初めて現れる位置) を全ての \(i, c\) に対して前計算しておけば，部分列DP の要領で \(T\) の各文字を最も早く現れる箇所から貪欲に選んでいく方法によって，\(O(M)\) で求められます．\(nxt(i, c)\) は後ろから順に決定していくことで，\(\sigma = 26\) として \(O(\sigma N)\) で計算可能です．

以上の方法で，\(O((\sigma + M)N)\) でこの問題を解くことができます．