题解 CF1163D 【Mysterious Code】

· · 题解

此题也可以使用 AC 自动机解决

首先可以看出是字典树有关的，显然要在字典树上跑 DP

但是如果加上一个不匹配字符就可能跑到另一个节点，这时就可以想到 AC 自动机

在 AC 自动机上每个节点记录这个节点表示的前缀的后缀是否包含串 s 和串 t，记f_{i,j}表示填到第i个位置，在字典树上第j个节点的最优答案，据此 DP 一下就完了

#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;
}