有两个仅包含小写英文字母的字符串 和 。现在要从字符串 中取出 个互不重叠的非空子串，然后把这 个子串按照其在字符串 中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串 相等？ 注意：子串取出的位置不同也认为是不同的方案。
链接
题解
设 表示字符串 的前 位和字符串 的前 位（必选 ），取出 个子串的方案数； 表示字符串 的前 位和字符串 的前 位（不必选 ），取出 个子串的方案数。
计算 时，考虑匹配到前一个字符时的方案数（最后一个子串加一个字符），和单独作为一个子串的方案数。
比较显然
边界为 。
需要滚动数组。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAXN = 1000;
const int MAXM = 200;
const int MAXK = 200;
const int MOD = 1e9 + 7;
int main() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
static char a[MAXN + 1], b[MAXM + 1];
scanf("%s\n%s", a, b);
static int f[2][MAXM + 1][MAXK + 1], g[2][MAXM + 1][MAXK + 1];
g[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
const int curr = i % 2, prev = !curr;
memset(f[curr], 0, sizeof(f[curr]));
memset(g[curr], 0, sizeof(g[curr]));
g[curr][0][0] = f[curr][0][0] = 1;
for (int j = 1; j <= m; j++) {
for (int t = 1; t <= std::min(j, k); t++) {
if (a[i - 1] == b[j - 1]) {
f[curr][j][t] = (f[prev][j - 1][t] + g[prev][j - 1][t - 1]) % MOD;
g[curr][j][t] = (g[prev][j][t] + f[curr][j][t]) % MOD;
#ifdef DBG
printf("g[%d][%d][%d] = %d\n", i, j, t, g[curr][j][t]);
printf("f[%d][%d][%d] = %d\n", i, j, t, f[curr][j][t]);
#endif
} else {
f[curr][j][t] = 0;
g[curr][j][t] = g[prev][j][t];
}
}
}
}
printf("%d\n", g[n % 2][m][k]);
return 0;
}