两个字符串s1，s2，求s2作为s1的子串（连续的和不连续的）出现的次数。

题目大意：两个字符串s1，s2，求s2作为s1的子串（连续的和不连续的）出现的次数。
思路：
设solve(n, m)为求s2作为s1的子串出现的次数，m为s1的长度，n为s2的长度。
如果s1和s2的最后字符相等，则分两种情况：假如s1的最后字符被考虑，则求solve(n-1, m-1)；若不考虑，求solve(n-1, m)；否则略过s1最后字符，求solve(n-1, m)。以这种思路递归很快可以写出来，注意初始条件：solve(0,0) = 1, solve(i, 0) = 1。
可以发现递归有重复计算存在，尝试动规。显然(n,m)的计算只和(n-1, m-1 or m)相关，则两次循环即可，还是注意初始条件。
实现：无
代码：

#include <iostream>
using namespace std;

#define MAXN    1010
int T, N, M;
string s1, s2;
// dp[i][j]: 
int dp[MAXN][MAXN];

// 递归
int solve(int n, int m) {
    if(m==0) return 1;
    if(n==0) return 0;

    if(s1[n-1] == s2[m-1]) {
        return solve(n-1, m-1) + solve(n-1, m);
    }else {
        return solve(n-1, m);
    }
}

int main() {
    cin >> T;
    while(T--) {
        cin >> N >> M;
        cin >> s1 >> s2;
        
        /*
        // 递归
        int ans = solve(N, M);
        cout << ans << endl;
        */

        // 动规
        for(int i=0; i<N; i++) {
            dp[i][0] = 1;
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M;j++) {
                if(s1[i]==s2[j]) {
                    dp[i+1][j+1] = dp[i][j] + dp[i][j+1];
                }else {
                    dp[i+1][j+1] = dp[i][j+1];
                }
            }
        }
        cout << dp[N][M] << endl;
    }
    return 0;
}

参考：https://www.geeksforgeeks.org/find-number-times-string-occurs-given-string/