病毒 bzoj-2938 Poi-2000
题目大意：给你n个01串，问是否存在一个无限长的01串使得这个01的任意子串都不等于给出的01串。
注释：All_length<=30,000
想法：裸题，介绍一下AC自动机。
什么是AC自动机？简单讲，就是Trie+KMP。KMP就是单模字符串匹配算法，基于next数组求出最长前缀后缀，增加匹配效率。多模匹配，就是好几个字符串之间匹配是否出现过或有什么性质等。这样效率太低，我们就把它们都扔到Trie树上。然后引进fail指针，就相当于next。
附上求fail的模板
void getfail()
{
while(!q.empty()) q.pop();
for(int i=0;i<26;i++)
{
if(a[0][i])
{
fail[a[0][i]]=0;
q.push(a[0][i]);
}
}
while(!q.empty())
{
int now=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(a[now][i])
{
fail[a[now][i]]=a[fail[now]][i];
q.push(a[now][i]);
}
else a[now][i]=a[fail[now]][i];
}
}
}
关于这道题，我们只需要给予Trie和fail指针跑出一个环即可，用两个数组vist和all_visit，分别表示当前走过的点和全局走过的点，visit实时更新即可。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 30001
using namespace std;
struct tree
{
int fail,vis[3];
bool end;
}a[N];
int cnt,num;
char s[N];
bool all_visit[N],visit[N];
void build(char *s)//建立Trie树
{
int l=strlen(s);
int now=0;
for(int i=0;i<l;i++)
{
int x=(s[i]-'0');
if(a[now].vis[x]==0)
{
a[now].vis[x]=++cnt;
}
now=a[now].vis[x];
}
a[now].end=true;
}
queue<int>q;
void bfs()
{
while(!q.empty()) q.pop();
for(int i=0;i<2;i++)//将根节点的两个儿子扔进队列
{
if(a[0].vis[i])
{
a[a[0].vis[i]].fail=0;
q.push(a[0].vis[i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<2;i++)
{
if(a[now].vis[i])
{
a[a[now].vis[i]].fail=a[a[now].fail].vis[i];
q.push(a[now].vis[i]);
if(a[a[a[now].fail].vis[i]].end)
{
a[a[now].vis[i]].end=true;
}
}
else
{
a[now].vis[i]=a[a[now].fail].vis[i];
}
}
}
}
void dfs(int d)
{
visit[d]=true;
for(int i=0;i<2;i++)
{
if(visit[a[d].vis[i]])
{
printf("TAK");
exit(0);
}
else if(!a[a[d].vis[i]].end&&!all_visit[a[d].vis[i]])
{
all_visit[a[d].vis[i]]=true;
dfs(a[d].vis[i]);
}
}
visit[d]=false;
}
int main()
{
int n;
cin >> n ;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
build(s);
}
a[0].fail=0;
bfs(),dfs(0);
printf("NIE");
return 0;
}
小结：AC自动机还是很强的qwq。