\(S\) の \(i\) 文字目 \((1\le i\le |S|)\) や \(T\) の \(i\) 文字目 \(1\le i\le |T|\) を \(S _ i,T _ i\) と書くこととします。

次のように \(\operatorname{dp} _ {i}[j]\ (1\le i\le |S|,0\le j\le |T|)\) を定めます。

• \(\operatorname{dp} _ i[j]\coloneqq S\) の部分文字列 \(S _ kS _ {k+1}\cdots S _ i\ (1\le k\le i)\) のうち、次の \(2\) つの条件を満たすものの個数
  • \(j=0\) もしくは部分列として \(T _ 1T _2\cdots T _ j\) を含む
  • \(j=|T|\) もしくは部分列として \(T _ 1T _ 2\cdots T _ {j+1}\) を含まない

これは、次のように計算することができます（配る 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}\]

求めるものは \(\displaystyle\sum _ {i=1} ^ {|S|}\sum _ {j=0} ^ {|T|-1}\operatorname{dp} _ i[j]\) です。 これは \(O(|S||T|)\) 時間で求めることができ、十分高速です。 答えを求めるのに、すべての空でない部分文字列の個数 \(\dfrac{|S|(|S|+1)}2\) から \(\displaystyle\sum _ {i=1} ^ {|S|}\operatorname{dp} _ i[|T|]\) を引いてもよいでしょう。

実装例は以下のようになります。 in-place に DP テーブルを更新すると、少し実装が楽になるかもしれません。

#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) { // S の各文字 s を順に見て
        ++dp.front();
        for (const auto i : views::enumerate(T) | views::filter([s](const auto& t){return s == get<1>(t);}) | views::reverse | views::keys) { // s = T[i] となる i について降順に
            dp[i + 1] += dp[i]; // dp テーブルを更新する
            dp[i] = 0;
        }
        ans += ranges::fold_left(dp | views::take(size(T)), 0UL, plus{}); // 答えに dp テーブルの合計を足す
    }
    cout << ans << endl;
    return 0;
}