【bzoj2938】病毒

Solution

　　这题的话。。一开始想的是不是上一个trie就消失了但是后来发现好像我还是太年轻qwq

　　比较容易联想到。。AC自动机，多串匹配嘛

　　然后就。。考虑一下AC自动机的匹配过程，就是一直沿着trie上的节点走然后没得走了就跳\(fail\)

　　那所以如果说我们要构造一个无限长的无法匹配到的串的话，首先在trie上面走的时候就不能碰到某个模式串的结尾节点，然后又因为要构造一个。。无限长的串。。那。。找一个环然后一直绕着走就好了

　　所以现在的问题就变成了，我们要在AC自动机上面找一个环，这个环中的每个点都不是结尾节点，并且每个点的\(fail\)都不是结尾节点（不然跳过去匹配一下就匹配上了，这个有点坑。。一开始WA了就是这个原因qwq）

　　那所以求完\(fail\)数组再从根dfs一下就好了

　　一个小trick就是为了。。方便的话。。我们在建\(fail\)的时候可以直接将失配的地方的\(ch\)直接指到\(fail\)跳转到的地方，这样就不用每次都借助\(fail\)来跳了（貌似是。。几百万年前机房的小伙伴给我科普的奇妙写法qwq）

　　代码大概长这个样子：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define MOD 1000000007

#define ll long long

using namespace std;

const int N=30010,AC=N,C=2;

int n,m;

char s[N];

namespace Ac{/*{{{*/

	queue<int> q;

	int ch[AC][C],cnt[AC],fail[AC],nok[AC],vis[AC];

	int tot,rt;

	void init(){tot=0; rt=0;}

	int newnode(){

		cnt[++tot]=0; return tot;

	}

	void insert(char *s,int len){

		int now=rt,c;

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

			c=s[i]-'0';

			if (!ch[now][c]) ch[now][c]=newnode();

			now=ch[now][c];

		}

		nok[now]=true;

	}

	void build_fail(){

		int u,v;

		q.push(rt);

		while (!q.empty()){

			v=q.front(); q.pop();

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

				if (!ch[v][i]) {ch[v][i]=ch[fail[v]][i];continue;}

				if (v){

					if (nok[ch[fail[v]][i]])

						nok[ch[v][i]]=true;

					fail[ch[v][i]]=ch[fail[v]][i];

				}

				else

					fail[ch[v][i]]=0;

				q.push(ch[v][i]);

			}

		}

	}

	bool dfs(int x){

		vis[x]=1;//ing

		int u;

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

			u=ch[x][i];

			if (nok[u]) continue;

			if (vis[u]==1||(vis[u]==0&&dfs(u))) return true;

		}

		vis[x]=-1;//end

		return false;

	}

	void solve(){

		build_fail();

		memset(vis,0,sizeof(vis));

		bool ans=false;

		ans=dfs(rt);

		if (ans) printf("TAK\n");

		else printf("NIE\n");

	}

};/*}}}*/

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	Ac::init();

	scanf("%d",&n);

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

		scanf("%s",s);

		Ac::insert(s,strlen(s));

	}

	Ac::solve();

}

巴特西

【bzoj2938】病毒

Solution

最新文章

热门文章