题解：P2679 [NOIP2015 提高组] 子串

www.luogu.com.cn

https://www.luogu.com.cn/problem/P2679

老师上课刚讲完这道题，来这里~~长个估值~~分享一下，顺便加深记忆。

定义 dp 状态

设 $f_{i,j,k}$ 表示从字符串 $A$ 的前 $i$ 个字符中，取出 $k$ 个非空子串，拼接后与字符串 $B$ 的前 $j$ 个字符相等的方案数。

状态转移

不取当前字符。
若第 $i$ 个字符不属于当前子串，则有 $f_{i,j,k}+=f_{i-1,j,k}$ 。
取当前字符, 拼接到新的子串。
若从位置 $i-p+1$ 到 $i$ 的子串等于 $B_{j-p+1:j}$ （即子串长度为 $p$ 且匹配成功），则有 $f_{i,j,k}+=f_{i-p,j-p,k-1}$ 。

这里 $p$ 的范围取决于当前 $A$ 和 $B$ 的匹配情况。

预处理可匹配长度

可以预处理一个二维数组 $ycl_{i,j}$ ，表示从 $A_i$ 和 $B_j$ 开始，最长能匹配的长度，判断 $A$ 的某段子串与 $B$ 的某段子串是否匹配。

优化

接着我们可以发现，每次是修改 $f_{i+1,j+1,k+1}$ 到 $f_{i+p,j+p,k+1}$ 的值，相当于是将一斜行上的值进行修改，所以可以进行差分。
由于只会从上一状态转移过来，所以可以把 $k$ 这一维滚掉：

用 $f_{i,j}$ 表示当前状态。
使用 $g_{i,j}$ 辅助存储下一状态。
在每次迭代 $k$ 时，将 $f$ 和 $g$ 交换，清空 $g$ 。

代码实现

cpp

#include<bits/stdc++.h>
using namespace std;
int n,m,kk,ycl[1010][210],MOD=1000000007;
string a,b;
signed main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>n>>m>>kk>>a>>b;
    vector<vector<int>> f(n+3,vector<int>(m+3,0));
    vector<vector<int>> g(n+3,vector<int>(m+3,0));
    f[0][0]=1;
    f[1][1]=-1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            int t=1;
            while(i+t<=n&&j+t<=m&&a[i+t-1]==b[j+t-1]) t++;
            ycl[i][j]=t-1;
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=m;j++){
    //         cout<<ycl[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    for(int k=0;k<=kk;k++){
        for(int i=0;i<=n;i++){
            for(int j=0;j<=m;j++){
                int p=ycl[i][j];
                if(i!=0&&j!=0) f[i][j]=(f[i-1][j-1]+f[i][j])%MOD;
                // cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j]<<endl;
                f[i+1][j]=(f[i+1][j]+f[i][j])%MOD;
                f[i+2][j+1]=(f[i+2][j+1]+MOD-f[i][j])%MOD;
                g[i+1][j+1]=(g[i+1][j+1]+f[i][j])%MOD;
                g[i+p+1][j+p+1]=(g[i+p+1][j+p+1]+MOD-f[i][j])%MOD;
            }
        }
        if(k==kk) cout<<f[n][m];
        swap(f,g);
        fill(g.begin(),g.end(),vector<int>(m+3,0));
    }
    return 0;
}