「BZOJ2938」[POI2000] 病毒
Description
二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
l 读入病毒代码；
l 判断是否存在一个无限长的安全代码；
l 将结果输出
Input
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。
Output
你应在在文本文件WIN.OUT的第一行输出一个单词：
l TAK——假如存在这样的代码；
l NIE——如果不存在。
Sample Input
3
01
11
00000
01
11
00000
Sample Output
NIE
题解
zky:
首先我们把所有串建一个AC自动机
方便起见我们直接把fail指针合并到子结点
如果一个串能无限长,也就是说它可以在AC自动机上一直进行匹配但就是匹配不上
也就是说匹配指针不能走到val为1的结点,设这个点为x
即root..x是一个病毒串
那么fail指针指向x的y也不能走
因为root..x是root..y的一个后缀
处理出来判断有向图是否有环
dfs即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<map> #include<set> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n; struct acm { int cnt; int next[30005][2]; int fail[30005],danger[30005],q[30005]; bool vis[30005],ins[30005]; char ch[30005]; acm(){ cnt=1; for(int i=0;i<2;i++)next[0][i]=1; } void insert(){ scanf("%s",ch); int now=1,l=strlen(ch); for(int i=0;i<l;i++) { if(!next[now][ch[i]-'0'])next[now][ch[i]-'0']=++cnt; now=next[now][ch[i]-'0']; } danger[now]=1; } void buildfail(){ int head=0,tail=1; q[0]=1;fail[0]=1; while(head!=tail) { int now=q[head];head++; for(int i=0;i<2;i++) { int v=next[now][i]; if(!v) { next[now][i]=next[fail[now]][i]; continue; } int k=fail[now]; while(!next[k][i])k=fail[k]; fail[v]=next[k][i]; danger[v]|=danger[next[k][i]]; q[tail++]=v; } } } bool dfs(int x){ ins[x]=1; for(int i=0;i<2;i++) { int v=next[x][i]; if(ins[v])return 1; if(vis[v]||danger[v])continue; vis[v]=1; if(dfs(v))return 1; } ins[x]=0; return 0; } }acm; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) acm.insert(); acm.buildfail(); if(acm.dfs(1))puts("TAK"); else puts("NIE"); return 0; } |
Subscribe
计数器 9787384
OI 课件=>
OI 课件=>