主要是两个优化：
1. 先写一个普通的DP（这个还是比较简单）dp[i][j]表示长度为i的S中包含长度为j的T的数量，dp[i][j] = s[i - 1]==t[j - 1]?dp[i-1][j-1] + dp[i-1][j] : dp[i-1][j];
2. 发现空间复杂度爆了，把二维DP换成滚动数组。
3. 发现时间爆了，对S做了一个预处理，记录26个字母出现的位置（注意要反向记录）。

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
const int M = 1000000007;
int dp[N];
unordered_map<char,vector<int>> hmap;

int solve(string &s,string &t){
    hmap.clear();
    if(s.size() < t.size())return 0;

    for(int i = t.size()-1;i>=0;i--){
        hmap[t[i]].push_back(i+1);
    }

    memset(dp,0,sizeof(dp));
    dp[0] = 1;

    int n = s.size(), m = t.size();
    for(int j = 1;j<=n;j++){

        vector<int> lst = hmap[s[j-1]];
        for(int i = 0;i<lst.size();i++){
            if(lst[i] > j)continue;
            else dp[lst[i]] = (dp[lst[i]] % M + dp[lst[i] - 1] % M) % M;
        }

        // for(int i = 0;i<=m;i++){
        //     cout<<dp[i]<<' ';
        // }
        // cout<<'\n';

    }
    return dp[m];

}

int main(){
    int n;cin>>n;
    while(n--){
        string s,t;
        cin>>s>>t;
        cout<<solve(s,t)<<'\n';
    }


}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla