【洛谷 P2444】 [POI2000]病毒（AC自动机）

这么多字符串，肯定是自动机啦。

先建出AC自动机，然后怎么表示一个安全代码没有病毒代码呢？

就是存在一条路径不经过有病毒代码段结尾的节点呗。

所以呢？有环啊！dfs一下救星了。

#include <cstdio>

#include <queue>

#include <cstring>

#include <cstdlib>

using namespace std;

struct Node{

    int fail, next[2], num;

}AC[1000010];

int n, u, cnt;

queue <int> q;

int vis[1000010], mark[1000010];

char a[2000010];

void insert(){

    int len = strlen(a + 1), w;

    u = 0;

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

        w = a[i] - '0';

        if(!AC[u].next[w])

          AC[u].next[w] = ++cnt;

        u = AC[u].next[w];

    }

    AC[u].num = 1;

}

void BuildFail(){

	u = 0;

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

       if(AC[u].next[i])

         q.push(AC[u].next[i]);

    while(q.size()){

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

        AC[u].num |= AC[AC[u].fail].num;

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

           if(AC[u].next[i]){

           	 q.push(AC[u].next[i]);

             AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i];

           }

           else

		     AC[u].next[i] = AC[AC[u].fail].next[i];

    }

}

void dfs(int x){

	if(AC[x].num) return;

	if(vis[x]){ printf("TAK\n"); exit(0); }

	if(mark[x]) return;

	vis[x] = mark[x] = 1;

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

	   if(AC[x].next[i])

	     dfs(AC[x].next[i]);

	vis[x] = 0;

}

int main(){

    scanf("%d", &n);

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

     	scanf("%s", a + 1);

    	insert();

    }

    BuildFail();

    dfs(0);

    printf("NIE\n");

    return 0;

}

巴特西

【洛谷 P2444】 [POI2000]病毒（AC自动机）

最新文章

热门文章