题目：
现在有两个字符串A和B，请你给出子串B在文本A中出现的次数（可以非连续出现）。即：设A={a1...an}，B={b1...bm}，请给出有多少组不同的I={i1...im}使得ai1=b1,ai2=b2...aim=bm。不幸的是，本题的子串长度也可能很长。由于答案可能过大，请输出对10007取余后的结果。
输入格式:
两行，每行一个字符串。第一行为字符串A，第二行为字符串B。（len(B)<=len(A)<104）
输出格式:
一行，一个整数，为子串出现次数mod10007。
输入样例:
aabbccddeede
abcde
输出样例:
56要求字符串B在A中出现了多少次，不要求连续（但要从左往右）
这是一道很简单的dp(听别人说的，但自己不会dp)
状态变量dp[i][j]表示 字符串A前i个字符包含字符串B前j个字符有多少个
状态转移方程：if(A[i]==B[j]) dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])%10007;
else dp[i][j] = dp[i-1][j];
dp[][]方程初始化: dp[i][0] = 1; 表示A前i个字符中含B前0个字符1个；
代码：
点击查看代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<deque>
#include<string>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 310000
#define N 200010
#define endl '\n'
#define exp 1e-8
#define lc p << 1
#define rc p << 1|1
#define lowbit(x) ((x)&-(x))
const double pi = acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
inline ULL read() {
ULL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
void print(ULL x) {
if (x > 9)print(x / 10);
putchar(x % 10 ^ 48);
}
int dp[10100][10010];
int main()
{
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
a = ' ' + a; b = ' ' + b;
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
{
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (a[i] == b[j]) dp[i][j] = (dp[i-1][j] + dp[i - 1][j - 1]) % 10007;
else dp[i][j] = dp[i - 1][j];
}
}
cout << dp[n][m] <<endl;
return 0;
}
/*也可以写滚动数组来优化空间
int dp[10100];
int main()
{
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
a = ' ' + a; b = ' ' + b;
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= 1; j--)
{
if (a[i] == b[j]) dp[j] = (dp[j - 1] + dp[j]) % 10007;
}
}
cout << dp[m];
return 0;
}
*/