题解：P2679 [NOIP2015 提高组] 子串
Luogu 题解：P2679 [NOIP2015 提高组] 子串 题解
老师上课刚讲完这道题，来这里长个估值分享一下，顺便加深记忆。
定义 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$。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #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 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;
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;
}
|
