【NOIP2015】子串
有两个仅包含小写英文字母的字符串 AA 和 BB。
现在要从字符串 AA 中取出 kk 个互不重叠的非空子串，然后把这 kk 个子串按照其在字符串 AA 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 BB 相等？
注意：子串取出的位置不同也认为是不同的方案。
输入格式
第一行是三个正整数 n,m,kn,m,k，分别表示字符串 AA 的长度，字符串 BB 的长度，以及问题描述中所提到的 kk，每两个整数之间用一个空格隔开。
第二行包含一个长度为 nn 的字符串，表示字符串 AA。
第三行包含一个长度为 mm 的字符串，表示字符串 BB。
输出格式
输出共一行，包含一个整数，表示所求方案数。
由于答案可能很大，所以这里要求输出答案对 10000000071000000007 取模的结果。
样例一
input
6 3 1
aabaab
aab
output
2
样例二
input
6 3 2
aabaab
aab
output
7
样例三
input
6 3 3
aabaab
aab
output
7
explanation
所有合法方案如下：（加下划线的部分表示取出的子串）
样例一：aab aab / aab aab
样例二：a ab aab / a aba ab / a a ba ab / aab a ab / aa b aab / aa baa b / aab aa b
样例三：a a b aab / a a baa b / a ab a a b / a aba a b / a a b a a b / a a ba a b / aab a a b
网上的题解还是很详细的，所以就直接复制一下，然后贴代码了，感谢
“*那么记一下思路吧，这道题是要压缩的，它会卡空间的，要滚动数组。
我们按照三维的来考虑，我们再记一个数组f[i][j][k]为选择第i位后的a串前i个b串前j个选择k个子串有几种组合方式
s[i][j][k]是a串前i个b串前j个选择k个子串有几种组合方式，f,s数组的差别是一个选了第i个，一个不一定选了第i个
然后和最长公共子串一样
f数组的递推思路：要是a的第i位能够和b的第j位匹配上，我们选择第i位当一个串是一种情况，
这个时候我们把s数组的s[i-1][j-1][k-1]转移过来就可以了，那么i-1显然也要和j-1匹配上才能多加上额外的一些情况，
如果i-1和j-1都匹配不上就不能再往左延伸了，所以如果a[i]!=b[j]相当于一个公共子串被切断一样，f[i][j][k]=0
所以：
f[i][j][k]=f[i-1][j-1][k]+s[i-1][j-1][k-1] (a[i]==b[j])
f[i][j][k]=0 (a[i]!=b[j])
s数组的递推思路：当a[i]==b[j]时，我们可以选i也可以不选，我们加上f数组就好了和不选的情况s[i-1][j][k]就可以了，
如果不相同那就肯定不选了，此时f数组为0，我们无需特判
s[i][j][k]=f[i][j][k]+s[i-1][j][k]
压缩的思路：由于我们的每次i都只与i-1有关，所以我们可以把第一维压缩掉，因为后面的j要用到j-1的情况，
所以我们从后往前更新，k同理，也是从后往前，然后要控制范围是min(K,j)*”
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define mod 1000000007
using namespace std;
int n,m,k;
int f[205][205], s[205][205];
char a[1005], b[205];
int main(){
scanf("%d%d%d", &n, &m, &k);
scanf("%s%s", a+1, b+1);
s[0][0]=1;
for(int i=1; i<=n; i++){
for(int j=m; j>=1; j--){
if(a[i] == b[j]) {
for(int h=min(k,j); h>=1; h--){
f[j][h] = (f[j-1][h] + s[j-1][h-1]) % mod;
s[j][h] = (s[j][h] + f[j][h]) % mod;
}
}
else fill(f[j], f[j] + min(k,j) + 1, 0);//区间赋值为0
}
}
printf("%d\n", s[m][k]);
return 0;
}