BZOJ2938: [Poi2000]病毒【AC自动机】

2938: [Poi2000]病毒

【题目描述】

传送门

【题解】

首先安全码肯定是一个子串无限循环,那么我们只要知道这个子串一个循环节不能被匹配,那么这个子串在自动机上不能遇到匹配点,并且形成环。
我们可以用DFS找到这个环。

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=3*1e4;
int n;
char ch[MAXN];
bool vis[MAXN],L[MAXN];
struct Acho{
    int Son[MAXN][2],pre[MAXN],cnt,que[MAXN],hd,tl;
    bool W[MAXN];
    void Insert(char *s){
        int Now=0,Len=strlen(s);
        for(int i=0;i<Len;i++){
            if(!Son[Now][s[i]-'0']) Son[Now][s[i]-'0']=++cnt;
            Now=Son[Now][s[i]-'0'];
        }
        W[Now]=1;
    }
    void Build(){
        hd=tl=0;
        for(int i=0;i<2;i++) if(Son[0][i]) que[++tl]=Son[0][i];
        while(hd^tl){
            int x=que[++hd];
            for(int i=0;i<2;i++)
            if(Son[x][i]){
                int f=pre[x];
                while(f&&!Son[f][i]) f=pre[f];
                pre[que[++tl]=Son[x][i]]=Son[f][i],
                W[Son[x][i]]|=W[Son[f][i]];
            }else Son[x][i]=Son[pre[x]][i];
        }
    }
    bool Fnd(int x){
        vis[x]=1;
        for(int i=0;i<2;i++)
        if(Son[x][i]){
            if(vis[Son[x][i]]) return 1;
            if(L[Son[x][i]]||W[Son[x][i]]) continue;
            L[Son[x][i]]=1;
            if(Fnd(Son[x][i])) return 1;
        }
        vis[x]=0;return 0;
    }
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",ch),Tre.Insert(ch);
    Tre.Build();
    printf(Tre.Fnd(0)?"TAK\n":"NIE\n");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部