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