[bzoj2938][Poi2000]病毒_AC自动机

时间:2024-04-06 22:35:30

病毒 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。