この問題は、各 \(i\) (\(1 \leq i \leq N\)) に対し、\(s\) の \(i\) 文字目から \(j\) 文字目からなる部分文字列が \(T\) を部分列として含まない最大の \(j\) を求め、各 \(i\) に対する \(j\) の範囲の長さの和を取ると解けます。

(自明に、\(S\) の \(i\) 文字目から \(j\) 文字目からなる部分文字列が \(T\) を部分列として含むなら、\(S\) の \(i\) 文字目から \(j+1\) 文字目からなる部分文字列も \(T\) を部分列として持つので、条件を満たす \(j\) は \(1\) つの範囲となる)

これは、貪欲に \(T\) の文字を順番に \(1\) 番左にあるものを取ればよく、これは \(S\) の文字とindexを持った配列を作っておいて、二分探索をすれば求められます。

よって、この問題が \(O(|S||T|\)\(log |S|)\) で解けます

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define pb push_back
#define all(x) (x).begin(), (x).end()

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string s,t;
    cin>>s>>t;
    int N=s.size(),M=t.size();
    vector<vector<int>>idx(26);
    for(int i=0;i<N;i++){
        idx[s[i]-'a'].pb(i);
    }
    for(int i=0;i<26;i++)idx[i].pb(N);
    ll ans=0;
    for(int i=0;i<N;i++){
        int rig=i-1;
        for(int j=0;j<M;j++){
            rig=*upper_bound(all(idx[t[j]-'a']),rig);
            if(rig==N)break;
        }
        ans+=(rig-i);
    }
    cout<<ans<<"\n";
}