有两个仅包含小写英文字母的字符串 A 和 B。
现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 B 相等？
注意：子串取出的位置不同也认为是不同的方案。
输入格式
第一行是三个正整数 n,m,k，分别表示字符串 A 的长度，字符串 B 的长度，以及问题描述中所提到的 k，每两个整数之间用一个空格隔开。
第二行包含一个长度为 n 的字符串，表示字符串 A。
第三行包含一个长度为 m 的字符串，表示字符串 B。
输出格式
输出共一行，包含一个整数，表示所求方案数。
由于答案可能很大，所以这里要求输出答案对 1000000007 取模的结果。
样例一
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
n≤1000 m≤200 k≤m
时间限制：1s
空间限制：128MB
思路：
其实在考场上看到这道动规题的时候，我知道必然要推一段时间，于是我跳过去打了T3，这道题打到11：45才打完，当时确实很紧张，紧张到算200*200=400000（汗），妥妥地爆了空间，这题并不是很难，写在博客是为了警醒自己。
接下来进入正题：首先这题很像lcs，一眼看过去我就大致确定了lcs的基础模型，于是我推了两个方程：
①当a[i]==b[j]时，方案可以从F[i-1,j-1,l-1]和F[i-1,j-1,l];
②当a[i]!=b[j]时，方案则从F[i-1,j,l],F[i,j-1,l]过来；
然而，我输了一遍样例，发现会大很多，于是我想了想，第一个方程中会包含一些不该被转移的方案被转移过来。然后我加了一个A数组，用以记最后一位相同的方案数加以转移，答案就得解了。
这题不滚动会卡空间，然而我滚动了还是卡空间了XD
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MOD 1000000007
#define N 2000//应该改成1000
typedef long long LL;
LL F[3][N][N],A[3][N][N];
int n,m,k;
char s1[N],s2[N];
int main(){freopen("substring.in","r",stdin);freopen("substring.out","w",stdout);scanf("%d%d%d",&n,&m,&k);scanf("%s",s1+1);scanf("%s",s2+1);F[0][0][0]=1;for (int i=1;i<=n;i++){F[i%2][0][0]=1;for (int j=1;j<=m;j++)for (int kk=1;kk<=k;kk++){F[i%2][j][kk]=A[i%2][j][kk]=0;if (s1[i]==s2[j]){if (s1[i]==s2[j]){F[i%2][j][kk]=(F[i%2][j][kk]+F[(i-1)%2][j-1][kk-1])%MOD;A[i%2][j][kk]=(A[i%2][j][kk]+F[(i-1)%2][j-1][kk-1])%MOD;}if (s1[i-1]==s2[j-1]&&s1[i]==s2[j]&&i!=1){F[i%2][j][kk]=(F[i%2][j][kk]+A[(i-1)%2][j-1][kk])%MOD;A[i%2][j][kk]=(A[i%2][j][kk]+A[(i-1)%2][j-1][kk])%MOD;}}F[i%2][j][kk]=(F[i%2][j][kk]+F[(i-1)%2][j][kk])%MOD;}}printf("%lld",F[n%2][m][k]%MOD);fclose(stdin);fclose(stdout);return 0;
}