洛谷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;
}