题解 CF1163D 【Mysterious Code】
土田共戈
2020-04-13 16:08:01
此题也可以使用 AC 自动机解决
首先可以看出是字典树有关的，显然要在字典树上跑 DP
但是如果加上一个不匹配字符就可能跑到另一个节点，这时就可以想到 AC 自动机
在 AC 自动机上每个节点记录这个节点表示的前缀的后缀是否包含串 s 和串 t，记$f_{i,j}$表示填到第$i$个位置，在字典树上第$j$个节点的最优答案，据此 DP 一下就完了
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define db double
#define INF 2147483647
#define LLINF 9223372036854775807
#define LL long long
using namespace std;
int inline read(){
int num=0,neg=1;char c=getchar();
while(!isdigit(c)){if(c=='-')neg=-1;c=getchar();}
while(isdigit(c)){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
return num*neg;
}
const int maxn=1010;
int n,l1,l2;char str[maxn],s[maxn],t[maxn];
int ch[maxn][26],fail[maxn],sum[maxn],f[maxn][maxn],cnt;
void insert(char *str,int n,int flg){
int now=0;
for(int i=1;i<=n;i++){
if(!ch[now][str[i]-'a'])ch[now][str[i]-'a']=++cnt;
now=ch[now][str[i]-'a'];
}sum[now]+=flg;
}queue<int>que;int q[maxn],r;
void bfs(){
que.push(0);
while(!que.empty()){
int x=que.front();q[++r]=x;que.pop();
if(!x){
for(int i=0;i<26;i++)
if(ch[0][i])fail[ch[0][i]]=0,que.push(ch[0][i]);continue;
}
for(int i=0;i<26;i++)
if(ch[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];que.push(ch[x][i]);
}else ch[x][i]=ch[fail[x]][i];
}for(int i=2;i<=r;i++)sum[q[i]]+=sum[fail[q[i]]];
}
int main()
{
scanf("%s",str+1);n=strlen(str+1);
scanf("%s",s+1);l1=strlen(s+1);insert(s,l1,1);
scanf("%s",t+1);l2=strlen(t+1);insert(t,l2,-1);bfs();
for(int i=0;i<=n;i++)
for(int j=0;j<=cnt;j++)f[i][j]=-INF/3;f[0][0]=0;
for(int i=0;i<n;i++){
for(int j=0;j<=cnt;j++){
if(f[i][j]==-INF/3)continue;
for(int k=0;k<26;k++){
if(str[i+1]!=k+'a'&&str[i+1]!='*')continue;int to=ch[j][k];
f[i+1][to]=max(f[i+1][to],f[i][j]+sum[to]);
}
}
}int ans=-INF;
for(int i=0;i<=cnt;i++)ans=max(ans,f[n][i]);
printf("%d",ans);return 0;
}
```