欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu2896 病毒侵袭(AC自动机)

程序员文章站 2022-06-06 20:31:51
...

题目来源:hdu2896 病毒侵袭

完整题目:

hdu2896 病毒侵袭(AC自动机)

hdu2896 病毒侵袭(AC自动机)

注意事项:

①MLE 32768KB卡限,这里用指针的AC自动机卡了32628KB过了,考虑用数组的AC自动机

②病毒小于等于3个也得排序啊

③在线输出和离线输出都可以

AC代码:

#include <iostream>
#include <algorithm> 
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <bitset> 
const int INF=0x3f3f3f3f;
const int mod=10007;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
//ascii码可见 开128数组比较靠谱 扩容 注意26只适用于小写字母的情况 
//这题有毒 多组输入没说 稍微开大一点空间就MLE 32768kb异常的坑 
struct acnode{
    int sum;
    int v;//代表是几号串的标号 
    acnode* next[128];
	acnode* fail;
    acnode(){
    	v=0;
        for(int i =0;i<128;i++)
            next[i]=NULL;
        fail= NULL;
        sum=0;
    }
};
acnode *root;
char s[10005],tmp[205];//搞离线 
int ans[15],n,m,final,mark[505];
acnode* newnode()
{
    acnode *p = new acnode();
    return p;
}
//插入函数
void Insert(char *s,int num)
{
    acnode *p = root;
    for(int i = 0; s[i]; i++)
    {
        int x = s[i];
        if(p->next[x]==NULL)
        {
            acnode *nn=newnode();
            p->next[x]=nn;
        }
        p = p->next[x];
    }
    p->sum++;
    p->v=num;
}
//获取fail指针,在插入结束之后使用
void getfail(){
    queue<acnode*> q;
	for(int i = 0 ; i < 128 ; i ++ )
	{
		if(root->next[i]!=NULL){
			root->next[i]->fail = root;
			q.push(root->next[i]);
		}
	}
    while(!q.empty())
	{
        acnode* tem = q.front();
        q.pop();
        for(int i = 0;i<128;i++)
		{
            if(tem->next[i]!=NULL)
            {
                acnode *p;
                if(tem == root)
				{
                    tem->next[i]->fail = root;
                }
                else
                {
                    p = tem->fail;
                    while(p!=NULL){
                        if(p->next[i]!=NULL){
                            tem->next[i]->fail = p->next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(p==NULL)
                        tem->next[i]->fail = root;
                }
                q.push(tem->next[i]);
            }
        }
    }
}
//匹配函数
int ac_automation(char *ch)
{
    acnode *p = root;
    int len = strlen(ch),tot=0;
    for(int i = 0; i < len; i++)
    {
        int x = ch[i];
        while(p->next[x]==NULL && p != root)//没匹配到,那么就找fail指针。
            p = p->fail;
        p = p->next[x];
        if(!p)
            p = root;
        acnode *temp = p;
        while(temp != root)
        {
           if(temp->sum >= 0)
           {
               if(temp->v&&!mark[temp->v])//标记一下不然可能会影响结果 别的失配的时候正好路过该单词尾 
			   {
			    ans[tot++]=temp->v;
			    mark[temp->v]=1;   //匹配过,不该改为0,不然下次就没法匹配了 
			   }
				
           }
           else break;
           temp = temp->fail;
        }
    }
    return tot;
}
void Delete(acnode* root)
{
	for(int i=0;i<128;++i)if(root->next[i])Delete(root->next[i]);
	delete root;
}
void init()
{
	mem(ans,0);
	final=0; 
}
int main()
{
	    while(~scanf("%d",&n))
		{ 
	    init();
    	root=newnode();
    	sci(n);
    	rep(i,1,n)
    	{
    		scanf("%s",tmp);
    		Insert(tmp,i);
    	}
    	getfail();
    	sci(m);
    	rep(i,1,m)
    	{
    	     scanf("%s",s);
    	     int num=ac_automation(s);
    	     if(num)sort(ans,ans+num);//坑比的排序,忽视了一直wa 
    		 rep(j,0,num-1)
    		 {
    		  if(!j)final++,printf("web %d:",i);
    		  printf(" %d",ans[j]);
    		  if(j==num-1)puts(""); 
    		 }
    		 mem(mark,0);
    	}
    	printf("total: %d\n",final);
    	Delete(root);
        }
        return 0;
}