题目描述 Description
有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串B相等?注意:子串取出的位置不同也认为是不同的方案。
输入描述 Input Description
第一行是三个正整数n,m,k,分别表示字符串A的长度,字符串B的长度,以及问题描述中所提到的k,每两个整数之间用一个空格隔开。
第二行包含一个长度为n的字符串,表示字符串A。 第三行包含一个长度为m的字符串,表示字符串B。
输出描述 Output Description
输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对1,000,000,007取模的结果。
样例输入 Sample Input
【Input1】
6 3 1
aabaab
aab
【Input2】
6 3 2
aabaab
aab
【Input3】
6 3 3
aabaab
aab
样例输出 Sample Output
【Output1】
2
【Output2】
7
【Output3】
7
数据范围及提示 Data Size & Hint
对于第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。
/* f[i][j][k][0/1]表示a匹配到i,b匹配到j,已经用了k个子串,且i用或不用时的方案数 转移方程: ①当i不使用时 f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1] ②当i使用时(a[i]=b[j]) f[i][j][k][1]=f[i-1][j-1][k][1]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k-1][0] 可以将第一维滚动 */ #include<iostream> #include<cstring> #include<cstdio> #define mod 1000000007 #define maxn 210 using namespace std; int n,m,p,s,f[2][maxn][maxn][2]; char A[maxn*5],B[maxn]; int main() { scanf("%d%d%d",&n,&m,&p); scanf("%s%s",A+1,B+1); for(int i=1;i<=n;i++) { f[i%2][1][1][0]=s; if(A[i]==B[1])f[i%2][1][1][1]=1,s++; for(int j=2;j<=m;j++) for(int k=1;k<=p;k++) { f[i%2][j][k][0]=(f[(i+1)%2][j][k][0]+f[(i+1)%2][j][k][1])%mod; if(A[i]==B[j]) f[i%2][j][k][1]=((f[(i+1)%2][j-1][k-1][1]+f[(i+1)%2][j-1][k][1])%mod+f[(i+1)%2][j-1][k-1][0])%mod; } for(int j=1;j<=m;j++) for(int k=1;k<=p;k++) f[(i+1)%2][j][k][1]=f[(i+1)%2][j][k][0]=0; } printf("%d ",(f[n%2][m][p][0]+f[n%2][m][p][1])%mod); return 0; }