P7456 题解

· · 题解

有一个显然的dp：

令 f_i 表示文本串前 i 位已经覆盖完的最小代价。

若 s[i,j] 是个模式串，显然有 f_j=\min(f_k+1)(i-1\le k<j)

多模式串匹配，考虑 AC 自动机。

对于所有模式串建出 ACAS ，易对文本串进行匹配。

由转移方程，求 f_j 时显然想让 i 最小，模式串就尽量大。匹配到的那个点到 fail 根上的所有点里，那些表示某模式串末尾的，就能和它的 len 取 \max 。这个不用每次求，直接预处理实现。

把这个 i 求出来，dp 就随便拿个数据结构实现即可。我用的是反向 ST 表。

my code:

#include<bits/stdc++.h>
using namespace std;
int n;char c[300010],cc[300010];
int ch[300010][26],cn=1,len[300010],fail[300010];
queue<int>q;
void build(){
    for(int i=0;i<26;i++)if(ch[1][i])fail[ch[1][i]]=1,q.push(ch[1][i]);else ch[1][i]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        len[u]=max(len[u],len[fail[u]]);
        for(int i=0;i<26;i++)if(ch[u][i])
            fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]);
        else ch[u][i]=ch[fail[u]][i];
    }
}
int dp[300010][20];
int ask(int l,int r){
    if(l>r)return 1e9+7;
    int k=log2(r-l+1);
    return min(dp[r][k],dp[l+(1<<k)-1][k]);
}
int main(){
    scanf("%d%s",&n,cc+1);
    for(int i=0;i<n;i++){
        scanf("%s",c);int l=strlen(c),u=1;
        for(int j=0;j<l;j++){
            if(!ch[u][c[j]-'a'])ch[u][c[j]-'a']=++cn;
            u=ch[u][c[j]-'a'];
        }
        len[u]=max(len[u],l);
    }
    build();int le=strlen(cc+1),u=1;
    memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
    for(int i=1;i<=le;i++){
        u=ch[u][cc[i]-'a'];
        dp[i][0]=ask(i-len[u],i-1)+1;
        for(int j=1;j<20;j++){
            if(i-(1<<j)+1<0)break;
            dp[i][j]=min(dp[i][j-1],dp[i-(1<<j-1)][j-1]);
        }
    }
    return printf("%d",dp[le][0]>1e9?-1:dp[le][0]),0;
}