题目：子串
思路：
大佬的思路
令f[i][j][kk][0/1]表示a的前i个，b的前j个，分为kk段，第i个取不取的方案数。
转移方程：
if(a[i]!=b[j]) {
f[val][j][kk][0]=(f[val^1][j][kk][0]+f[val^1][j][kk][1])%md;f[val][j][kk][1]=0;
} else {
f[val][j][kk][0]=(f[val^1][j][kk][0]+f[val^1][j][kk][1])%md;f[val][j][kk][1]=((f[val^1][j-1][kk-1][0]+f[val^1][j-1][kk-1][1])%md+f[val^1][j-1][kk][1])%md;
}
代码：
#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 1000
#define maxm 200
#define md 1000000007int n,m,k;
char a[maxn+5],b[maxm+5];
int f[5][maxm+5][maxm+5][2];int main() {
read(n),read(m),read(k);scanf("%s",a+1);scanf("%s",b+1);f[1][0][0][0]=f[0][0][0][0]=1;int val=1;for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
for(int kk=1;kk<=k;kk++) {
if(a[i]!=b[j]) {
f[val][j][kk][0]=(f[val^1][j][kk][0]+f[val^1][j][kk][1])%md;f[val][j][kk][1]=0;} else {
f[val][j][kk][0]=(f[val^1][j][kk][0]+f[val^1][j][kk][1])%md;f[val][j][kk][1]=((f[val^1][j-1][kk-1][0]+f[val^1][j-1][kk-1][1])%md+f[val^1][j-1][kk][1])%md;}}}val^=1;}printf("%d",(f[n&1][m][k][1]+f[n&1][m][k][0])%md);return 0;
}