LG2444/BZOJ2938 「POI2000」病毒 AC自动机

问题描述

I \(\mathrm{AC}\)自动机

\(\mathrm{AC}\)自动机是一种多模式串匹配算法，本萌新今天刚学了它qwq

约定在构造\(\mathrm{AC}\)自动机的过程中，\(\mathrm{Trie}\)树上的边和由于\(\mathrm{AC}\)自动机中这一句：

else ch[x][i]=ch[fail[x]][i];

所新建的边为实边。

也就是\(x\)到\(ch[x][0]\)和\(ch[x][1]\)的边为实边。

II 危险！

什么样的字符串是有病毒的？包含了某个模式串的文本串。

这样的文本串一定在AC自动机上经过一个字符串的结尾节点。

我们称这样的节点是危险的。

III 解法

想象一下，假如在AC自动机上有一个环，我就可以让这个文本串一直在这个环上跑，转啊转啊转。

就像最短路有了负环一样。

所以，只要在AC自动机上，存在一个环，使得这个环上和从根到这个环的路径上，所有的点都不是危险节点，就有解，否则无解。

IV \(\mathrm{code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') {

		ch=getchar();fh=-1;

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

int n;

int ch[300000][2],tot;

bool ed[300000];

int fail[300000],root;

string s;

int chk(char s){

	return s-'0';

}

void insert(){

	int siz=s.size();int p=root;

	for(int i=0;i<siz;i++){

		int d=chk(s[i]);

		if(!ch[p][d]) ch[p][d]=++tot;

		p=ch[p][d];

	}

	ed[p]=1;

}

void pre(){

	queue<int>q;

	for(int i=0;i<2;i++){

		if(ch[root][i]) fail[ch[root][i]]=root,q.push(ch[root][i]);

	}

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=0;i<2;i++){

			if(ch[x][i]){

				fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);

				if(ed[ch[fail[x]][i]]) ed[ch[x][i]]=1;

			}

			else ch[x][i]=ch[fail[x]][i];

		}

	}

}

bitset<300000>ins;

void dfs(int x){

	if(ins[x]){

		puts("TAK");exit(0);

	}

	ins[x]=1;

	for(int i=0;i<2;i++){

		if(!ch[x][i]||ed[ch[x][i]]) continue;

		dfs(ch[x][i]);

	}

	ins[x]=0;

}

int main(){

	read(n);

	for(register int i=1;i<=n;i++){

		cin>>s;insert();

	}

	pre();dfs(root);

	puts("NIE");

	return 0;

}

巴特西