BZOJ2938-蒲公英云

BZOJ2938

#

BZOJ2938-病毒

题意：

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

解法：

因为是多字符串匹配，所以我们依旧考虑AC自动机。
建立AC自动机，在不能走每个单词最后一个字母的前提下，如果某个字符串在自动机上无法匹配，则说明可以找到无限长的字符串。

CODE：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define N 30010 struct Edge { int to,from; }e[N * 2 + 10]; struct Trie { int fail,nxt[2]; bool flag; }tree[N]; char ch[N]; int m,n,num,cnt,head[N],d[N]; queue<int> q; inline void add_edge(int x,int y) { e[++cnt].from = y; e[cnt].to = head[x]; head[x] = cnt; } void insert(char *s) { int len = strlen(s + 1); int x = 1; for(int i = 1 ; i <= len ; i++) { if(!tree[x].nxt[s[i] - '0']) tree[x].nxt[s[i] - '0'] = ++num; if(tree[x].flag) tree[tree[x].nxt[s[i] - '0']].flag = 1; x = tree[x].nxt[s[i] - '0']; } tree[x].flag = 1; } void build() { q.push(1); while(!q.empty()) { int u = q.front(); q.pop(); if(tree[tree[u].fail].flag) tree[u].flag = 1; for(int i = 0 ; i <= 1 ; i++) { if(tree[u].nxt[i]) { q.push(tree[u].nxt[i]); if(u == 1) tree[tree[u].nxt[i]].fail = 1; else tree[tree[u].nxt[i]].fail = tree[tree[u].fail].nxt[i]; } else { if(u == 1) tree[u].nxt[i] = 1; else tree[u].nxt[i] = tree[tree[u].fail].nxt[i]; } } } } int main() { scanf("%d",&n); num++; while(n--) { scanf("%s",ch+1); insert(ch); } build(); for(int i = 1 ; i <= num ; i++) { if(tree[i].flag) continue; for(int j = 0 ; j < 2 ; j++) { if(tree[tree[i].nxt[j]].flag) continue; add_edge(i,tree[i].nxt[j]); d[tree[i].nxt[j]]++; } } for(int i = 1 ; i <= num ; i++) if(d[i] == 0) q.push(i); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x] ; i ; i = e[i].to) { int u = e[i].from; d[u]--; if(d[u] == 0) q.push(u); } } for(int i = 1 ; i <= num ; i++) { if(d[i]) { puts("TAK"); // system("pause"); return 0; } } puts("NIE"); /* for(int i = 1 ; i <= num ; i++) printf("%d ",d[i]);*/ //system("pause"); return 0; }