有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串B相等？注意：子串取出的位置不同也认为是不同的方案。
第一行是三个正整数n，m，k，分别表示字符串A的长度，字符串B的长度，以及问题描述中所提到的k，每两个整数之间用一个空格隔开。
第二行包含一个长度为n的字符串，表示字符串A。 第三行包含一个长度为m的字符串，表示字符串B。
输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对1,000,000,007取模的结果。
【Input1】
6 3 1
aabaab
aab
【Input2】
6 3 2
aabaab
aab
【Input3】
6 3 3
aabaab
aab
【Output1】
2
【Output2】
7
【Output3】
7
对于第1组数据：1≤n≤500，1≤m≤50，k=1；
对于第2组至第3组数据：1≤n≤500，1≤m≤50，k=2；
对于第4组至第5组数据：1≤n≤500，1≤m≤50，k=m；
对于第1组至第7组数据：1≤n≤500，1≤m≤50，1≤k≤m；
对于第1组至第9组数据：1≤n≤1000，1≤m≤100，1≤k≤m；
对于所有10组数据：1≤n≤1000，1≤m≤200，1≤k≤m。
所有合法方案如下：（加下划线的部分表示取出的子串）
样例一：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] 表示A串匹配到i B串匹配到j 用了k个子串
转移的话 f[i][j][k]=f[i-1][j-1][k]+f[i-1][j-1][k-1]分别表示i是不是建立了一个新的子串
当然这是我们会发现 这样的状态是默认了i用了 显然i可以不用 也就是说这样就遗漏了许多状态
我们重新定义一下他 加一维01表示i用了没用 f[i][j][k][0或1]
这样转移就要分开考虑01
f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]因为i没有用 所以不会有新串k不变 B串也不会更新匹配j不变
f[i][j][k][1]=
+f[i-1][j-1][k-1][0]
+f[i-1][j-1][k][1]
+f[i-1][j-1][k-1][1]
AC代码:
#include<cstdio>
#define maxn 1010
#define mod 1000000007
using namespace std;
int n,m,s,f[][maxn][maxn][],sum;
char s1[maxn],s2[maxn];
int main(){
scanf("%d%d%d",&n,&m,&s);
scanf("%s%s",s1+,s2+);
for(int i=;i<=n;i++){
f[i&][][][]=sum;
if(s1[i]==s2[]) sum++,f[i&][][][]=;
for(int j=;j<=m;j++){
for(int k=;k<=s;k++){
f[i&][j][k][]=(f[i-&][j][k][]+f[i-&][j][k][])%mod;
if(s1[i]!=s2[j])continue;
f[i&][j][k][]=((f[i-&][j-][k-][]+f[i-&][j-][k-][])%mod+f[i-&][j-][k][])%mod;
}
}
for(int j=;j<=m;j++){
for(int k=;k<=s;k++){
f[i-&][j][k][]=f[i-&][j][k][]=;
}
}
}
printf("%d\n",(f[n&][m][s][]+f[n&][m][s][])%mod);
return ;
}
以下为自己以前写的代码（感觉自己写的更优）
题解：（dp）
f(k,i,j)表示分了k段，用了第一个串中的前i个数字，已经构成了第二个串的前j个的方案数
f(k,i,j)=∑f(k−1,l,j−1) 当s1[i]==s2[j]且s1[i−1]!=s2[j−1]其中0<l<i
∑f(k−1,l,j−1)+f(k,i−1,j−1) 当s1[i]==s2[j]且s1[i−1]==s2[j−1]其中0<l<i
第一个转移是独立开辟出一个部分的可能数，第二个是算上之前就已经分了k个部分后把第k个部分扩大的方案数。还是比较好理解的，当然f数组要滚动第一维，不然会爆内存。
我觉得这一道题的难度，都和当年乌龟棋在当时的难度差不多了。但这道题的70分算法O(nm2k)比较好写，所以拉不卡差距。
相信大家在看了我的状态转移之后能想出O(nmk)的方法。其实我们需要维护的就只是那一个∑用一个tmp数组保存一下就好了（详见代码）
AC代码（int）：
#include<cstdio>
using namespace std;
#define N 1005
#define M 205
#define mod 1000000007
int n,m,K;
int f[][N][M];
char a[N],b[M];
int main(){
scanf("%d%d%d",&n,&m,&K);
scanf("%s%s",a+,b+);
int k=;
for(int i=;i<=n;i++) f[][i][]=;
for(int h=;h<=K;h++){
k^=;
for(int i=;i<=n;i++) f[k][i][h-]=;
for(int j=h;j<=m;j++){
for(int i=j;i<=n;i++){
if(a[i]==b[j]){
f[k][i][j]=((f[k][i-][j]+f[k][i-][j-])%mod+f[k^][i-][j-])%mod;
if(i>=) f[k][i][j]=(f[k][i][j]-f[k][i-][j-]+mod)%mod;
}
else f[k][i][j]=f[k][i-][j];
}
}
}
printf("%d\n",f[k][n][m]);
return ;
}
AC代码（long long）：
#include<cstdio>
using namespace std;
#define N 1005
#define M 205
#define mod 1000000007
int n,m,K;
long long f[][N][M];
char a[N],b[M];
int main(){
scanf("%d%d%d",&n,&m,&K);
scanf("%s%s",a+,b+);
int k=;
for(int i=;i<=n;i++) f[][i][]=;
for(int h=;h<=K;h++){
k^=;
for(int i=;i<=n;i++) f[k][i][h-]=;
for(int j=h;j<=m;j++){
for(int i=j;i<=n;i++){
if(a[i]==b[j]){
f[k][i][j]=f[k][i-][j]+f[k][i-][j-]+f[k^][i-][j-];
if(i>=){
f[k][i][j]-=f[k][i-][j-];
if(f[k][i][j]<) f[k][i][j]+=mod;
}
}
else f[k][i][j]=f[k][i-][j];
if(f[k][i][j]>=mod) f[k][i][j]%=mod;
}
}
}
printf("%lld",f[k][n][m]);
return ;
}
附测试点7
ps：注意mod时不要越界
in
gglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbbglbbgglbbgglbbgglbbggltbgglbbgglbbgglbbgglbbgglbbgglbbgglgbgglbbgglbbgdlbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbvgglbbgglbbgglbbgglbbgglbbgglbbgglbbggllbgglbbgglbbgglbbgglbbgggbblglbbgglbbaglbbgglbbcglbbgglbbgglbbgglbbgglbbgglkbgglbbgglbbgglbbgblbbnglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgggbbgglbbgglbbgglbbgglbbgggbbgglbbgglbbgglbbgulbbgglbbgglbbgglbbgglbbgglbbgglbgglbbgglbbgglbbgglbbb
gglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbbgglbb
out