题解 P2444 【[POI2000]病毒】

no_one_cm_Fe_in_hand · 2019-03-13 19:07:37 · 题解

活见鬼了总

好吧，考察了一下AC自动机的性质特别是对fail指针的理解。（苯蒟蒻显然不理解） 先看看样例。 （假设您现在已经依据样例画好了一棵trie树） 经过反复观察 发现可以考虑搜一下（因为成功找到后就退出，所以不会炸····） 搞一个vis数组，若在搜索过程中又遇到了标记处，即可说明循环了，就成功了 然后记得回溯 然后您可能会打出如下代码：

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
int n,c[N][2],tot=0,cnt[N];
bool end[N];
int fail[N];
char ch[30010];
inline void insert(char *p){
    int now=0,len=strlen(p);
    for(int i=0;i<len;++i){
        int s=p[i]-'0';
        if(!c[now][s])c[now][s]=++tot;
        now=c[now][s];
    }
    end[now]=1;
}
queue<int> q;
inline void build(){
    int now=0;
    for(int i=0;i<2;++i){
        if(c[now][i]) fail[c[now][i]]=now,q.push(c[now][i]);
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=0;i<2;++i){
            if(c[x][i]) fail[c[x][i]]=c[fail[x]][i],q.push(c[x][i]);
            else c[x][i]=c[fail[x]][i];
        }
    }
}
bool vis[N];
bool check(int now){
    vis[now]=1;
    for(int i=0;i<2;++i){
        if(vis[c[now][i]]) return 1;
        if(!end[c[now][i]]){
            if(check(c[now][i])) return 1;
        } 
    }
    vis[now]=0;
    return 0;
}
int main()
{
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%s",ch),insert(ch);
    build();
    if(check(0)) cout<<"TAK";else cout<<"NIE"<<endl;
}

结果挂了73feng。。。 然而只要第26行加上

end[c[x][i]]|=end[c[fail[x]][i]]

即可。你懂的呀