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自动机+判环。如果当匹配时存在环，说明存在，反之不行。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#define MAXN 1000010
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
inline int read(){
int x=
0,f=
1;
char ch=
getchar();
for(;!isdigit(ch);ch=
getchar())
if(ch==
'-')
f=-
1;
for(;isdigit(ch);ch=
getchar())
x=x*
10+ch-
'0';
return f*
x;
}
int n;
queue <
int>
Q;
char input[
300010];
int tree[
300010][
2],total=
1,isend[
300010];
int vis[
300010],nxt[
300010],book[
300010];
inline void insert(
char *
s){
int l=
strlen(s);
int u=
1;
REP(i,0,l-
1){
int c=s[i]-
'0';
if(!tree[u][c]) tree[u][c]=++
total;
u=
tree[u][c];
}
isend[u]=
1;
return ;
}
inline void getnext(){
tree[0][
0]=tree[
0][
1]=
1;
nxt[1]=
0;
Q.push(1);
while(!
Q.empty()){
int u=
Q.front();
Q.pop();
REP(c,0,
1){
if(!tree[u][c]) tree[u][c]=
tree[nxt[u]][c];
else{
int k=
nxt[u];
nxt[tree[u][c]]=
tree[nxt[u]][c];
isend[tree[u][c]]=isend[tree[u][c]]|
isend[tree[nxt[u]][c]];
Q.push(tree[u][c]);
}
}
}
return ;
}
inline bool dfs(
int x){
vis[x]=
1;
for(
int i=
0;i<
2;i++
)
{
int v=
tree[x][i];
if(vis[v])
return 1;
if(book[v] ||
isend[v])
continue;
book[v]=
1;
if(dfs(v))
return 1;
}
vis[x]=
0;
return 0;
}
int main(){
in(n);
REP(i,1,n){
scanf("%s",input);
insert(input);
}
getnext();
if(dfs(
1)) cout<<
"TAK"<<
endl;
else cout<<
"NIE"<<
endl;
return 0;
}
转载于:https://www.cnblogs.com/jason2003/p/9709280.html
相关资源：JAVA上百实例源码以及开源项目
