hdu 2896 病毒侵袭 (ac自动机)
题意：给出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}