首页 > 代码库 > NOIP2015 子串

NOIP2015 子串

#149. 【NOIP2015】子串

有两个仅包含小写英文字母的字符串 AA 和 BB。

现在要从字符串 AA 中取出 kk 个互不重叠的非空子串,然后把这 kk 个子串按照其在字符串 AA 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 BB 相等?

注意:子串取出的位置不同也认为是不同的方案。

输入格式

第一行是三个正整数 n,m,kn,m,k,分别表示字符串 AA 的长度,字符串 BB 的长度,以及问题描述中所提到的 kk,每两个整数之间用一个空格隔开。

第二行包含一个长度为 nn 的字符串,表示字符串 AA。

第三行包含一个长度为 mm 的字符串,表示字符串 BB。

输出格式

输出共一行,包含一个整数,表示所求方案数。

由于答案可能很大,所以这里要求输出答案对 10000000071000000007 取模的结果。

样例一

input

6 3 1aabaabaab

output

2

样例二

input

6 3 2aabaabaab

output

7

样例三

input

6 3 3aabaabaab

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

限制与约定

测试点编号nn的规模mm的规模kk的规模
1n500n≤500m50m≤50k=1k=1
2k=2k=2
3
4k=mk=m
5
6kmk≤m
7
8n1000n≤1000m100m≤100
9
10m200m≤200

时间限制:1s1s

空间限制:128MB128MB

题解:

//参考blog.sengxian.com

※先定义:s[i][j][k]为字符串A第i-1位对应字符串B第j-1位所达到的种类数,f[i][j][k]为A的i-1位和B的j-1位正好配对时所达到的种类数。

※转移方程1:那么很容易得到:s[i][j][k]=s[i-1][j][k]+f[i][j][k],即当前阶段的种类数=上一阶段未使用i-1位的种类数+使用i-1位的种类数。

※转移方程2:那么现在考虑怎样转移f[i][j][k],要分两种情况。

      1.当A(i-1) ≠ B(j-i)时,很明显f[i][j][k]=0

                  2.当A(i-1) = B(j-i)时,就又回到选与不选的问题上来了。所以,又分两种情况,一是直接和i-1与j-1配对的情况并未同一个子串,二是不并,新成立一个子串

      可知:

                0     (A(i-1) ≠ B(j-i))

        f[i][j][k]=

                f[i-1][j-1][k]+s[i-1][j-1][k-1]  (A(i-1) = B(j-i))

#104939#149. 【NOIP2015】子串ksq2013100112ms4100kbC++565b2016-10-28 17:16:59

程序如下:

#include<cstdio>#include<cstring>#include<iostream>#define MXN 1100#define md 1000000007#define fx(x,a,b) for(x=a;x<=b;x++)#define fy(x,a,b) for(x=a;x>=b;x--)using namespace std;int N,M,K,i,j,k,s[MXN][MXN],f[MXN][MXN];char s1[MXN],s2[MXN];int main(){    scanf("%d%d%d",&N,&M,&K);    getchar();    gets(s1);    gets(s2);    s[0][0]=1;    fx(i,1,N)fy(j,M,1)        if(s1[i-1]==s2[j-1])            fy(k,min(K,j),1)                f[j][k]=(s[j-1][k-1]+f[j-1][k])%md,s[j][k]=(s[j][k]+f[j][k])%md;        else fill(f[j],f[j]+min(K,j)+1,0);    printf("%d\n",s[M][K]);    return 0;}

 

NOIP2015 子串