www.luogu.com.cn
https://www.luogu.com.cn/problem/P2679
老师上课刚讲完这道题，来这里长个估值分享一下，顺便加深记忆。
定义 dp 状态
设 fi,j,kf_{i,j,k} 表示从字符串 AA 的前 ii 个字符中，取出 kk 个非空子串，拼接后与字符串 BB 的前 jj 个字符相等的方案数。
状态转移
- 不取当前字符。
若第 ii 个字符不属于当前子串，则有 fi,j,k+=fi−1,j,kf_{i,j,k}+=f_{i-1,j,k}。 - 取当前字符, 拼接到新的子串。
若从位置 i−p+1i-p+1 到 ii 的子串等于 Bj−p+1:jB_{j-p+1:j} （即子串长度为 pp 且匹配成功），则有 fi,j,k+=fi−p,j−p,k−1f_{i,j,k}+=f_{i-p,j-p,k-1}。 
这里 pp 的范围取决于当前 AA 和 BB 的匹配情况。
预处理可匹配长度
可以预处理一个二维数组 ycli,jycl_{i,j}，表示从 AiA_i 和 BjB_j 开始，最长能匹配的长度，判断 AA 的某段子串与 BB 的某段子串是否匹配。
优化
- 接着我们可以发现，每次是修改 fi+1,j+1,k+1f_{i+1,j+1,k+1} 到 fi+p,j+p,k+1f_{i+p,j+p,k+1} 的值，相当于是将一斜行上的值进行修改，所以可以进行差分。
- 由于只会从上一状态转移过来，所以可以把 kk 这一维滚掉：
- 用 fi,jf_{i,j} 表示当前状态。
- 使用 gi,jg_{i,j} 辅助存储下一状态。
- 在每次迭代 kk 时，将 ff 和 gg 交换，清空 gg。
代码实现
#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;
}