hdu 2896 病毒侵袭 (ac自动机)

hdu 2896 题目链接

题意:给出n个病毒,然后给出m个网站,然后问每个网站中有哪些病毒,以及有病毒的网站的个数。

需要注意病毒和网站都需要按从小到达排列输出。

思路:ac自动机,需要记录病毒id...然后。。因为病毒的id忘记排序wa了好多发。。智力减2.

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月16日 星期二 19时53分24秒
  4File Name :code/hdu/2896.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <stack>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <deque>
 19#include <ctime>
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33vector <int>ans;
 34struct Trie
 35{
 36    struct Node
 37    {
 38	Node *nxt[128];
 39	Node *fail;
 40	int val;
 41	Node()
 42	{
 43	    for ( int i = 0 ; i < 128 ; i++) nxt[i] = NULL;
 44	    val = 0;
 45	    fail = NULL;
 46	}
 47    };
 48    Node *root;
 49    void init()
 50    {
 51	root = new Node();
 52    }
 53    void Insert(char *s,int num)
 54    {
 55	int len = strlen(s);
 56	Node *u = root;
 57	for ( int i = 0 ; i < len ;i++)
 58	{
 59	    int v = s[i]-32;
 60	    if (u->nxt[v]==NULL) u->nxt[v] = new Node();
 61	    u = u->nxt[v];
 62	}
 63	u->val = num;
 64    }
 65    void getFail()
 66    {
 67	root->fail = root;
 68	queue<Node*>Q;
 69	for ( int i = 0 ; i < 128 ; i++)
 70	{
 71	    if (root->nxt[i]==NULL)
 72		root->nxt[i] = root;
 73	    else
 74	    {
 75		root->nxt[i]->fail = root;
 76		Q.push(root->nxt[i]);
 77	    }
 78	}
 79	while (!Q.empty())
 80	{
 81	    Node * cur = Q.front();
 82	    Q.pop();
 83	    for ( int i = 0 ; i < 128 ; i++)
 84		if (cur->nxt[i]==NULL)
 85		    cur->nxt[i] = cur->fail->nxt[i];
 86		else
 87		{
 88		    cur->nxt[i]->fail = cur->fail->nxt[i];
 89		    Q.push(cur->nxt[i]);
 90		}
 91	}
 92    }
 93    bool Search(char *s)
 94    {
 95	int len = strlen(s);
 96	Node *u = root;
 97	ans.clear();
 98	bool ok = false;
 99	for ( int i = 0 ; i < len ; i++)
100	{
101	    int v  = s[i]-32;
102	    u = u->nxt[v];
103	    Node *tmp = u;
104	    while (tmp!=root&&tmp->val>0)
105	    {
106		ans.push_back(tmp->val);
107//  		tmp->val = 0;
108		tmp = tmp->fail;
109		ok = true;
110	    }
111	}
112	return ok;
113    }
114}ac;
115int n,m;
116char str[10025];
117int main()
118{
119	#ifndef  ONLINE_JUDGE 
120	freopen("code/in.txt","r",stdin);
121  #endif
122	while (~scanf("%d",&n))
123	{
124	    ac.init();
125	    for ( int i = 1 ; i <= n ; i++)
126	    {
127		scanf("%s",str);
128//		cout<<"str:"<<str<<endl;
129		ac.Insert(str,i);
130	    }
131	    ac.getFail();
132	    int tot = 0 ;
133	    scanf("%d",&m);
134	    for ( int i = 1 ; i <= m ; i++)
135	    {
136		scanf("%s",str);
137//		cout<<"i:"<<i<<" str:"<<str<<endl;
138		if (ac.Search(str))
139		{
140		    tot++;
141		    printf("web %d:",i);
142		    sort(ans.begin(),ans.end()); //要求按顺序
143		    int siz = ans.size();
144		    for ( int i = 0 ; i < siz; i ++)
145			printf(" %d",ans[i]);
146		    printf("\n");
147		}
148	    }
149	    printf("total: %d\n",tot);
150	}
151  #ifndef ONLINE_JUDGE  
152  fclose(stdin);
153  #endif
154    return 0;
155}