noip2015Day2T2-子串

题目描述 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。

——————————————————————————题解

迟到一年的整理,然而看着看着有思路了还是不会写,orz

那么记一下思路吧,这道题是要压缩的,它会卡空间的,要滚动数组。

我们按照三维的来考虑,我们再记一个数组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 <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define mo 1000000007
#define siji(i,x,y) for(int i=(x);i<=(y);i++)
#define gongzi(j,x,y) for(int j=(x);j>=(y);j--)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);i++)
#define sigongzi(j,x,y) for(int j=(x);j>(y);j--)
#define pii pair<int,int>
#define fi first
#define se second
#define mo 1000000007
using namespace std;
typedef long long ll;
int n,m,k;
int f[][],s[][];
char a[],b[];
int main(int argc, char const *argv[])
{
//freopen("f1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
scanf("%s%s",a+,b+);
s[][]=;//如果有第一个相同我们就转移了
siji(i,,n) {
gongzi(j,m,) {
if(a[i]==b[j]) {
gongzi(h,min(k,j),) {//相等的话开始递推,数组里原先存着的是i-1,我们更新成i
f[j][h]=(f[j-][h]+s[j-][h-])%mo;
s[j][h]=(s[j][h]+f[j][h])%mo;
}
}
else fill(f[j],f[j]+min(k,j)+,);//不相等就是0
}
}
printf("%d\n",s[m][k]);
}
上一篇:Spring Boot实战之逐行释义HelloWorld


下一篇:【Shiro】小读Shiro Filter