首页 > 代码库 > HDU 2896 病毒侵袭 （AC自动机）

HDU 2896 病毒侵袭 （AC自动机）

2024-07-09 07:41:00   227人阅读


题意：给你n个病毒串，m个网站，问每个网站包含有哪些有病毒的网站，输出病毒编号。

最后输出有多少个有病毒的网站。


附：AC自动机详解

Sample Input
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc
 

Sample Output
web 1: 1 2 3
total: 1
PS：web 2 没有病毒


#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
const int kind = 94;

struct node
{
	node *fail;
	node *next[kind];
	int count;
	node()
	{
		fail = NULL;
		count = 0;
		memset(next,0,sizeof(next));
	}
}*q[1000200*2];
char keyword[220],str[10010];
int head,tail;
void insert(char *str,node *root,int num)
{
	node *p=root;
	int i=0,index;
	while(str[i])
	{
		index = str[i] - ' ';
		if(p->next[index]==NULL)
			p->next[index] = new node();
		p = p->next[index];
		i++;
	}
	p->count=num;
}

void build_ac(node *root)
{
	int i;
	root->fail=NULL;
	q[head++]=root;
	while(head!=tail)
	{
		node *temp = q[tail++];
		node *p=NULL;
		for(i=0;i<kind;i++)
		{
			if(temp->next[i]!=NULL)
			{
				if(temp==root)	
					temp->next[i]->fail=root;//失败指针指向root
				else 
				{
					p = temp->fail;
					while(p!=NULL)
					{
						if(p->next[i]!=NULL)
						{
							temp->next[i]->fail=p->next[i];
							break;
						}
						p=p->fail;
					}
					if(p==NULL)
						temp->next[i]->fail=root;
				}
				q[head++]=temp->next[i];
			}
		}
	}
}
int vis[550];
int num[550];
int query(char *str,node *root)
{
	int i=0,cnt=0,index,len=strlen(str);
	node *p=root;
	while(str[i])
	{
		index = str[i]-' ';
		while(p->next[index]==NULL&&p!=root)
			p = p->fail;
		p=p->next[index];
		p=(p==NULL)?root:p;
		node *temp = p;
		while(temp!=root)
		{

			if(temp->count!=0)
				cnt++;
			vis[temp->count]=1;
			temp=temp->fail;
		}
		i++;
	}
	return cnt;
}

int main()
{
	int n,m;
	while(~scanf("%d",&n))
	{
		head=tail=0;
		node *root = new node();
		getchar();
		for(int i=1;i<=n;i++)
		{
			gets(keyword);
			insert(keyword,root,i);
		}
		build_ac(root);
		int total=0;
		scanf("%d",&m);
		for(int j=1;j<=m;j++)
		{
			scanf("%s",str);
			memset(vis,0,sizeof(vis));
			int k=query(str,root);
			if(k==0)
				continue;
			printf("web %d:",j);
			for(int i=1;i<=n;i++)
				if(vis[i])
					printf(" %d",i);
			printf("\n");
			total++;
		}
		printf("total: %d\n",total);

	}
	return 0;
}

/*
3
aaa
ab
cc
2
aaabcc
abbccaa

*/


联系
我们