@Jerusalem
2015-11-11T19:35:09.000000Z
字数 1956
阅读 1340
我们观察到可以构造出字符串满足题意的充分必要条件是,以病毒代码构造的Trie图有环。
让我们考虑命题的证明,充分性是显然的,下证必要性。
假设构造出了满足题意的字符串S,那么对于S[i],其在AC自动机上对应节点及其后缀链接必然是非单词的。很容易发现,遍历了所有对应节点后,下一个节点一定会形成环。
Q.E.D
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int maxnode=30005,sigma=2;
struct Trie{
int tot;
int ch[maxnode][sigma];
int val[maxnode];
int f[maxnode];
bool danger[maxnode];
int last[maxnode];
bool ins[maxnode];
bool used[maxnode];
Trie(){
tot=1;
memset(ch,0,sizeof(ch));
memset(danger,false,sizeof(danger));
memset(f,0,sizeof(f));
memset(last,0,sizeof(last));
memset(ins,false,sizeof(ins));
memset(used,false,sizeof(used));
}
inline int idx(char a){
return a-'0';
}
void Clear(){
tot=1;
memset(danger,false,sizeof(danger));
memset(ch[0],0,sizeof(ch[0]));
memset(used,false,sizeof(used));
memset(ins,false,sizeof(ins));
}
int newnode(){
memset(ch[tot],0,sizeof(ch[tot]));
return tot++;
}
void Insert(string s){
int len=s.length();
int u=0;
for(int i=0;i<len;i++){
if(ch[u][idx(s[i])]==0)
ch[u][idx(s[i])]=newnode();
u=ch[u][idx(s[i])];
}
danger[u]=true;
}
void Build(){
queue<int> Q;
while(!Q.empty())
Q.pop();
for(int i=0;i<sigma;i++)
if(ch[0][i]){
Q.push(ch[0][i]);
last[ch[0][i]]=f[ch[0][i]]=0;
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<sigma;i++){
if(ch[u][i]==0){
ch[u][i]=ch[f[u]][i];
continue;
}
int v=ch[u][i];
Q.push(v);
int r=f[u];
while(r&&ch[r][i]==0)
r=f[r];
f[v]=ch[r][i];
danger[v]|=danger[f[v]];
}
}
}
bool HaveRing(int from){
ins[from]=true;
for(int i=0;i<sigma;i++){
if(ins[ch[from][i]])
return true;
if(danger[ch[from][i]]||used[ch[from][i]])
continue;
used[from]=true;
if(HaveRing(ch[from][i]))
return true;
}
ins[from]=false;
return false;
}
};
Trie Aho_Corasick;
string S;
int n;
void Solve()
{
Aho_Corasick.Build();
if(Aho_Corasick.HaveRing(0))
cout<<"TAK";
else
cout<<"NIE";
}
void ReadData()
{
freopen("BZOJ2938.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>S;
Aho_Corasick.Insert(S);
}
}
void Close()
{
fclose(stdin);
fclose(stdout);
}
int main()
{
ReadData();
Solve();
Close();
return 0;
}