bzoj 2938 AC自动机

根据题意建出trie图,代表单词的点不能走,直接或间接指向它的点也不能走。这样的话如果能在图中找到一个环的话就是TAK,否则是NIE。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 30005
using namespace std;
int n;bool flag;
int ch[N][];
bool yes[N][];
char s[N];int cnt;
bool ok[N];
void inn()
{
int now=;
int l=strlen(s);
for(int i=;i<l;i++)
{
if(!ch[now][s[i]-''])ch[now][s[i]-'']=++cnt,yes[now][s[i]-'']=;
now=ch[now][s[i]-''];
}
ok[now]=;
}
int f[N];
int vis[N],in[N];
queue<int>q;
void dfs(int x)
{
// cout<<x<<endl;
// cout<<in[1]<<"SS"<<endl;
vis[x]=;in[x]=;
for(int i=;i<;i++)
{
if(!vis[ch[x][i]])
{
if(!ok[ch[x][i]])
{
dfs(ch[x][i]);
}
}
else if(in[ch[x][i]])
{
flag=;
}
}
in[x]=;
}
bool fail()
{
for(int i=;i<;i++)if(ch[][i])q.push(ch[][i]);
while(!q.empty())
{
int tmp=q.front();q.pop();
for(int i=;i<;i++)
{
int u=ch[tmp][i];
if(!u)
{
ch[tmp][i]=ch[f[tmp]][i];continue;
}
f[u]=ch[f[tmp]][i];
if(ok[f[u]])ok[u]=;
q.push(u);
}
}
dfs();
if(flag)return ;
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s",s);inn();
}
//cout<<f[5]<<endl;
if(fail())puts("TAK");
else puts("NIE");
return ;
}
上一篇:[.net 面向对象程序设计进阶] (11) 序列化(Serialization)(三) 通过接口 IXmlSerializable 实现XML序列化 及 通用XML类


下一篇:Atitit php序列化 php的serialize序列化和json序列化