[vijos1982][NOIP2015]子串

Description

有两个仅包含小写英文字母的字符串 $A$ 和 $B$ 。现在要从字符串 $A$ 中取出 $k$ 个互不重叠的非空子串，然后把这 $k$ 个子串按照其在字符串 $A$ 中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串 $B$ 相等？注意：子串取出的位置不同也认为是不同的方案。

Input

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

第二行包含一个长度为 $n$ 的字符串，表示字符串 $A$ 。

第三行包含一个长度为 $m$ 的字符串，表示字符串 $B$ 。

Output

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

由于答案可能很大，所以这里要求输出答案对 $10^9+7$ 取模的结果。

Sample Input

6 3 2
aabaab
aab

Sample Output

HINT

$1$leq$n$leq$1000,1$leq$m$leq$200,1$leq$k$leq$m.$

Solution

$f[i][j][k][0/1]$ 表示 $A[1..i]$ 中的 $k$ 个子串与 $B[1..j]$ 相等的方案数(0表示不取 $A[i]$ ,1表示取)

$f[i][j][k][0]=f[i-1][j][k][0/1]$

$f[i][j][k][1]=f[i-1][j-1][k-1][0/1]+f[i-1][j-1][k][1](A[i]==B[j])$

滚动数组优化空间复杂度.

#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 205
#define N 1005
#define K 1000000007
using namespace std;
int f[2][M][M][2],n,m,k;
char a[N],b[M];
inline void init(){
    scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1);
    f[0][0][0][0]=1;
    for(int i=1,p,q;i<=n;++i){
        p=i&1;q=p^1;
        f[p][0][0][0]=1;
        for(int j=1;j<=m;++j)
            for(int l=1;l<=k;++l){
                f[p][j][l][0]=(f[q][j][l][0]+f[q][j][l][1])%K;
                if(a[i]==b[j]) f[p][j][l][1]=((f[q][j-1][l][1]+f[q][j-1][l-1][0])%K+f[q][j-1][l-1][1])%K;
                else f[p][j][l][1]=0;
            }
    }
    printf("%d
",(f[n&1][m][k][0]+f[n&1][m][k][1])%K);
}
int main(){
    freopen("str.in","r",stdin);
    freopen("str.out","w",stdout);
    init();
    fclose(stdin);
    fclose(stdout);
    return 0;
}