Steven_MengのBlog

传送门

考虑一下最长公共子序列的求法:

我们可以加一位$k$,表示$kmp$匹配到了哪一位。

我们可以这么理解,执行求$next[]$后,运行$Insert(ch,j)$($j$是上一次匹配到的位置),当$ch,j$,返回值肯定是固定的,表示这一次匹配到的位置,于是列出$dp[i+1][j+1][Insert(A[i+1],k)]=dp[i][j][k]+1)$的$dp$方程。

1
2
3
4
5
inline int Insert(char ch,int j){
while (j&&ch!=P[j+1]) j=nex[j];
if (ch==P[j+1]) j++;
return j;
}

代码:

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define MAXN 205
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
char A[MAXN],B[MAXN],P[MAXN];
int nex[MAXN],dp[MAXN][MAXN][MAXN];
int n,m,p;
inline void Build(){
int j=0;
for (register int i=2;i<=p;++i){
while (j&&P[i]!=P[j+1]) j=nex[j];
if (P[i]==P[j+1]) j++;
nex[i]=j;
}
}
inline int Insert(char ch,int j){
while (j&&ch!=P[j+1]) j=nex[j];
if (ch==P[j+1]) j++;
return j;
}
inline void chkmax(int &a,int b){
if (b>a) a=b;
}
int main(){
m=read(),n=read(),p=read();
scanf("%s",A+1);
scanf("%s",B+1);
scanf("%s",P+1);
Build();
for (register int i=0;i<=m;++i){
for (register int j=0;j<=n;++j){
for (register int k=0;k<p;++k){
if (i+1<=m&&j+1<=n&&A[i+1]==B[j+1]){
chkmax(dp[i+1][j+1][Insert(A[i+1],k)],dp[i][j][k]+1);
}
chkmax(dp[i+1][j][k],dp[i][j][k]);
chkmax(dp[i][j+1][k],dp[i][j][k]);
}
}
}
int ans=0;
for (register int i=0;i<p;++i){
ans=max(ans,dp[m][n][i]);
}
printf("%d\n",ans);
}

 评论