两个字符串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    1010int 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/