洛谷P2679 [NOIP2015 提高组] 子串 题解

题目链接：P2679 [NOIP2015 提高组] 子串

题意：

有两个仅包含小写英文字母的字符串 $A$ 和 $B$。

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

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

输出答案对 $10^9+7$ 取模的结果。

对于所有 $10$ 组数据： $1\le n \le 1000,~1 \le m \le 200,~1 \le d \le m$。

显然的字符串类型dp

一个原始的思路是：

设 $f_{i,j,k}$ 表示仅考虑 $A$ 的前 $i$ 个字符，$B$ 匹配到第 $j$ 个字符，用了 $k$ 个子串的方案数。

然后发现我们并不知道 $A_i$ 是否与 $B_j$ 匹配，无法转移

于是状态就变成了

设 $f_{i,j,k}$ 表示仅考虑 $A$ 的前 $i$ 个字符，$B$ 匹配到第 $j$ 个字符，用了 $k$ 个子串，且 $A_i$ 为最后一个匹配字符的方案数。

这样就可以转移了

$$\\f_{i,j,k} = \begin{cases} 1,&,i=j=k=0 \\\\f_{i-1,j,k}&,A_i \ne B_j \\\\f_{i-1,j,k}+\sum_{t=1}^{p+1} f_{i-t,j-t,k-1}&,\forall d \in [0,p], A_{i-d} = B_{j-d} \, \land \, A_{i-p-1} \ne B_{j-p-1} \end{cases}$$

显然 $i$ 这一维可以用滚动数组滚掉

那么 $\sum_{t=1}^{p+1} f_{i-t,j-t,k-1}$ 怎么处理呢

其实我们已经在之前的计算中把 $f_{i-t,j-t,k-1}$ 计算出来了

考虑动态维护一个前缀和，在遇到 $A_i\ne B_j$ 的时候中断，具体见代码

时间复杂度 $O(nmk)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(205)

const int p=1e9+7;
char a[1005],b[N];
int n,m,d,f[N][N],sum[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    f[0][0]=1;
    cin >> n >> m >> d >> a >> b;
    for(int i=1; i<=n; i++)
        for(int j=m; j>=1; j--)
            for(int k=d; k>=1; k--)
            {
                if(a[i-1]==b[j-1])
                    sum[j][k]=sum[j-1][k]+f[j-1][k-1];
                else sum[j][k]=0;
                f[j][k]=(f[j][k]+sum[j][k]%p)%p;
            }
    cout << f[m][d] << '\n';
    return 0;
}