P7456 [CERC2018] The ABCD Murderer 题解

huangleyi0129 · 2025-01-04 23:07:09 · 题解

ACAM 部分显然。

对每个点贪心，必然选长度最大的串。

设 f_i=i-maxlen。

倒着扫，考虑当前的覆盖区间 [u,n]（初始为 [f_n,n]），贪心地从中选出 f_i 最小的（具体地，扫一遍即可，见代码）。

设 u= \min f_i。

如果 v < u，则更新 u 为 v。

否则无解，贪心正确性显然。

注意特判 f_n=n。

时间复杂度 O(n)，目前最优解。

码风比较丑

#include<bits/stdc++.h>
using namespace std;
const int N=300005,S=26;
int trie[N][S],fail[N],f[N],is[N],n,m,k,ans=1;
char s[N],t[N];
void init()
{
    queue<int>q{};
    q.emplace(0);
    int u;
    while(!q.empty())
    {
        u=q.front(),is[u]=max(is[u],is[fail[u]]),q.pop();
        for(int i=0;i<26;++i)
            if(!trie[u][i])
                trie[u][i]=trie[fail[u]][i];
            else
                fail[trie[u][i]]=u==0?0:trie[fail[u]][i],q.emplace(trie[u][i]);
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>m>>s+1,n=strlen(s+1);
    int len,u,v;
    for(int i=1;i<=m;++i)
    {
        cin>>t+1,len=strlen(t+1);
        u=0;
        for(int j=1;j<=len;++j)
        {
            if(!trie[u][t[j]-'a'])
                trie[u][t[j]-'a']=++k;
            u=trie[u][t[j]-'a'];
        }
        is[u]=len;
    }
    init();
    u=0;
    for(int i=1;i<=n;++i)
    {
        u=trie[u][s[i]-'a'];
        f[i]=i-is[u];
    }
    u=v=f[n];
    if(f[n]==n)
    {
        cout<<"-1";
        return 0;
    }
    for(int i=n-1;i>=1;--i)
    {
        v=min(v,f[i]);
        if(i==u)
        {
            if(v>=u)
            {
                cout<<"-1";
                return 0;
            }
            u=v,++ans;
        }
    }
    cout<<ans;
    return 0;
}