Let \(S _ i,T _ i\) denote the \(i\)-th character of \(S\) \((1\le i\le |S|)\) and \(T\) \(1\le i\le |T|\), respectively.

Define \(\operatorname{dp} _ {i}[j]\ (1\le i\le |S|,0\le j\le |T|)\) as follows:

• \(\operatorname{dp} _ i[j]\coloneqq\) the number of substrings \(S _ kS _ {k+1}\cdots S _ i\ (1\le k\le i)\) of \(S\) such that:
  • \(j=0\) or the substring contains \(T _ 1T _2\cdots T _ j\) as a subsequence;
  • \(j=|T|\) or the substring does not contain \(T _ 1T _ 2\cdots T _ {j+1}\) as a subsequence.

This DP (Dynamic Programming) can be computed as follows. (It might be easier to implement as a distributing DP.)

\[\begin{aligned}\operatorname{dp} _ i[j]={}&\begin{cases}1&\quad&(j=0\wedge S _ i\ne T _ 1)\\0&&(\text{otherwise})\end{cases}\\&{}+\begin{cases}1&\quad&(j=1\wedge S _ i=T _ 1)\\0&&(\text{otherwise})\end{cases}\\&{}+\begin{cases}\operatorname{dp} _ {i-1}[j]&\quad&(j\lt|T|\wedge S _ i\ne T _ {j+1})\\0&&(\text{otherwise})\end{cases}\\&{}+\begin{cases}\operatorname{dp} _ {i-1}[j-1]&\quad&(S _ i=T _ j)\\0&&(\text{otherwise}).\end{cases}\end{aligned}\]

What we want to find is \(\displaystyle\sum _ {i=1} ^ {|S|}\sum _ {j=0} ^ {|T|-1}\operatorname{dp} _ i[j]\). This can be evaluated in \(O(|S||T|)\) time, which is fast enough. To find the answer, one may subtract \(\displaystyle\sum _ {i=1} ^ {|S|}\operatorname{dp} _ i[|T|]\) from the number of all non-empty substrings \(\dfrac{|S|(|S|+1)}2\).

The following is sample code. Updating the DP table in-place may help simplify the implementation.

#include <iostream>
#include <string>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    using namespace std;
    string S, T;
    cin >> S >> T;

    vector<unsigned> dp(size(T) + 1);

    unsigned long ans = 0;
    for (const auto s : S) { // Inspect each character s of S in order
        ++dp.front();
        for (const auto i : views::enumerate(T) | views::filter([s](const auto& t){return s == get<1>(t);}) | views::reverse | views::keys) { // for each i with s = T[i], in descending order
            dp[i + 1] += dp[i]; // update the DP table
            dp[i] = 0;
        }
        ans += ranges::fold_left(dp | views::take(size(T)), 0UL, plus{}); // add the sum of the DP table to the answer
    }
    cout << ans << endl;
    return 0;
}