• 热门专题

HDU3065病毒侵袭持续中(AC自动机)

作者:  发布日期:2014-06-24 20:39:51
Tag标签:自动机  病毒  
  • 中文题不解释

     

    Sample Input
    3
    AA
    BB
    CC
    ooxxCC%dAAAoen....END

    Sample Output
    AA: 2
    CC: 1
    输出病毒出现的次数!

     

     

    #include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    const int kind = 26;
    const int M = 1005;
    struct node
    {
    	node *fail;
    	node *next[kind];
    	int count;
    	node()
    	{
    		fail = NULL;
    		count = 0;
    		memset(next,0,sizeof(next));
    	}
    }*q[50*M];
    char keyword[1005][55],str[2000010];
    int head,tail;
    void insert(char *str,node *root,int num)
    {
    	node *p=root;
    	int i=0,index;
    	while(str[i])
    	{
    		index = str[i] - 'A';
    		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[1005];
    void query(char *str,node *root)
    {
    	int i=0,cnt=0,index,len=strlen(str);
    	node *p=root;
    	while(str[i])
    	{
    		if(str[i]<'A'||str[i]>'Z')
    		{
    			p=root;
    			i++;
    			continue;
    			
    		}
    		index = str[i]-'A';
    		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)
    		{
    			vis[temp->count]++;
    			temp=temp->fail;
    		}
    		i++;
    	}
    }
    
    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[i]);
    			insert(keyword[i],root,i);
    		}
    		build_ac(root);
    		scanf("%s",str);
    		memset(vis,0,sizeof(vis));
    		query(str,root);
    		for(int i=1;i<=n;i++)
    			if(vis[i])
    				printf("%s: %d
    ",keyword[i],vis[i]);
    	}
    	return 0;
    }
    

     

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规