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

Sample Output

NIE 思路： 首先将所有病毒串建一棵AC自动机。 想象一个无限长的安全代码存在，那么拿它到AC自动机上匹配，它会一直匹配但是一直匹配不成功。 也就是说匹配的时候不能匹配到End为1的结点(设为x)，且fail指针指向终点的点(设为y)也不能匹配到，因为root..x是root..y的一个后缀。 而要无限长，即一直匹配，就说明在匹配过程中会遇上一个环。 所以就是在AC自动机上看有没有环就行了。

感觉每做一道AC自动机的题就重新学一遍AC自动机

#include <bits/stdc++.h> #define ll long long using namespace std; const int p=10007; const int N=1e6+10; const int M=5e5+10; int n,T; char s[N]; struct acmach {int Next[M][2],Fail[M];bool End[M];bool vis[N],in[N];int root,L;int newnode(){for (int i=0;i<2;i++) Next[L][i]=-1;End[L]=0;return L++;}void init(){L=0;root=newnode();for (int i=0;i<N;i++) vis[i]=in[i]=0;}void Insert(char s[]){int len=strlen(s);int now=root;for (int i=0;i<len;i++){if (Next[now][s[i]-'0']==-1)Next[now][s[i]-'0']=newnode();now=Next[now][s[i]-'0'];}End[now]=1;}void build(){queue<int>q;Fail[root]=root; for (int i=0;i<2;i++)if (Next[root][i]==-1) Next[root][i]=root; else{Fail[Next[root][i]]=root;q.push(Next[root][i]);}while (!q.empty()){int now=q.front(); q.pop();End[now]|=End[Fail[now]]; //对于File指向End的点也不能访问到for (int i=0;i<2;i++)if (Next[now][i]==-1) Next[now][i]=Next[Fail[now]][i]; else{Fail[Next[now][i]]=Next[Fail[now]][i]; q.push(Next[now][i]);}}}bool dfs(int x){in[x]=1;for (int i=0;i<2;i++){int v=Next[x][i];if (in[v]) return 1;if (vis[v] || End[v]) continue;vis[v]=1;if (dfs(v)) return 1;}in[x]=0;return 0;} }ac; int main() {ac.init();scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%s",s);ac.Insert(s);}ac.build();if (ac.dfs(ac.root)) printf("TAK\n");else printf("NIE\n");return 0; } View Code

转载于:https://www.cnblogs.com/tetew/p/11545214.html

总结

以上是生活随笔为你收集整理的BZOJ2938:[POI2000] 病毒的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。