HDU2896 病毒侵袭(AC自动机)

描述

当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~
但网路上总有那么些网站，开始借着民众的好奇心，打着介绍日食的旗号，大肆传播病毒。小t不幸成为受害者之一。小t如此生气，他决定要把世界上所有带病毒的网站都找出来。当然，谁都知道这是不可能的。小t却执意要完成这不能的任务，他说：“子子孙孙无穷匮也！”（愚公后继有人了）。
万事开头难，小t收集了好多病毒的特征码，又收集了一批诡异网站的源码，他想知道这些网站中哪些是有病毒的，又是带了怎样的病毒呢？顺便还想知道他到底收集了多少带病毒的网站。这时候他却不知道何从下手了。所以想请大家帮帮忙。小t又是个急性子哦，所以解决问题越快越好哦~~

输入

第一行，一个整数 $N （ 1 <= N <= 500 ）$

输出

依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。 web 网站编号: 病毒编号病毒编号 …

冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。最后一行输出统计信息，如下格式

total: 带病毒网站数

冒号后有一个空格。

样例

输入

3
aaa
bbb
ccc
2
aaabbbccc
bbaacc

输出

web 1: 1 2 3
total: 1

思路

AC自动机模板题，只需要对AC自动机的代码稍微进行一下修改即可

但是有一些细节需要注意

三个坑点
- 字符串中字符都是ASCII码可见字符（不包括回车）
- 按网站编号从小到大输出
- 需要多次进行匹配，因此不可以删除字符串的序列标记(详情键见代码)

代码

  1 /*
  2  * =========================================================================
  3  *
  4  *       Filename:  B.cpp
  5  *
  6  *           Link:  http://acm.hdu.edu.cn/showproblem.php?pid=2896
  7  *
  8  *        Version:  1.0
  9  *        Created:  2018/09/02 11时45分16秒
 10  *       Revision:  none
 11  *       Compiler:  g++
 12  *
 13  *         Author:  杜宁元 (https://duny31030.top/), duny31030@126.com
 14  *   Organization:  QLU_浪在ACM
 15  *
 16  * =========================================================================
 17  */
 18 #include <bits/stdc++.h>
 19 using namespace std;
 20 #define clr(a, x) memset(a, x, sizeof(a))
 21 #define rep(i,a,n) for(int i=a;i<=n;i++)
 22 #define pre(i,a,n) for(int i=a;i>=n;i--)
 23 #define ll long long
 24 #define max3(a,b,c) fmax(a,fmax(b,c))
 25 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 26 const double eps = 1e-6;
 27 const int INF = 0x3f3f3f3f;
 28 const int mod = 1e9 + 7;
 29 const int N = 1e6+100;
 30 struct node
 31 {
 32     int son[128];
 33     int fail;
 34     int count;
 35     int number;
 36 }ac[N];
 37 int tot = 0;
 38 void init()
 39 {
 40     for(int i = 0;i < N;i++)
 41     {
 42         memset(ac[i].son,0,sizeof ac[i].son);
 43         ac[i].count = 0;
 44         ac[i].fail = 0;
 45         ac[i].number = 0;
 46     }
 47 }
 48 
 49 void Insert(char *s,int num)
 50 {
 51     int len = strlen(s);
 52     int now = 0;
 53     int tmp;
 54     for(int i = 0;i < len;i++)
 55     {
 56         tmp = s[i];
 57         if(ac[now].son[tmp] == 0)
 58             ac[now].son[tmp] = ++tot;
 59         now = ac[now].son[tmp];
 60     }
 61     ac[now].count++;
 62     ac[now].number = num;
 63 }
 64 
 65 void MakeFail()
 66 {
 67     queue<int> q;
 68     for(int i = 0;i < 128;i++)
 69     {
 70         if(ac[0].son[i] != 0)
 71         {
 72             ac[ac[0].son[i]].fail = 0;
 73             q.push(ac[0].son[i]);
 74         }
 75     }
 76     while(!q.empty())
 77     {
 78         int u = q.front();
 79         q.pop();
 80         for(int i = 0;i < 128;i++)
 81         {
 82             if(ac[u].son[i] != 0)
 83             {
 84                 ac[ac[u].son[i]].fail = ac[ac[u].fail].son[i];
 85                 q.push(ac[u].son[i]);
 86             }
 87             else 
 88                 ac[u].son[i] = ac[ac[u].fail].son[i];
 89         }
 90     }
 91 }
 92 
 93 int Query(char *s,int &no,int *a)
 94 {
 95     int len = strlen(s);
 96     int now = 0,ans = 0,tmp;
 97     for(int i = 0;i < len;i++)
 98     {
 99         tmp = s[i];
100         now = ac[now].son[tmp];
101         for(int t = now;t && ac[t].count != -1;t = ac[t].fail)
102         {
103             if(ac[t].number > 0)
104             {
105                 a[no++] = ac[t].number;
106             }
107             ans += ac[t].count;
108             // 注意这里 不可以在查询后将count修改为-1 
109             // 因为需要进行多次查询
110             // ac[t].count = -1;
111         }
112     }
113     return ans;
114 }
115 char s[210];
116 char Ts[10100];
117 int main()
118 {
119     ios
120 #ifdef ONLINE_JUDGE 
121 #else 
122         freopen("in.txt","r",stdin);
123     // freopen("out.txt","w",stdout); 
124 #endif
125     int N,M;
126     scanf("%d",&N);
127     for(int i = 1;i <= N;i++)
128     {
129         scanf("%s",s);
130         Insert(s,i);
131     }
132     ac[0].fail = 0;
133     MakeFail();
134     scanf("%d",&M);
135     int total = 0;
136     for(int i = 1;i <= M;i++)
137     {
138         int a[5];
139         clr(a,0);
140         int no = 1;
141         scanf("%s",Ts);
142         // printf("%s
",Ts);
143         int tmp = Query(Ts,no,a);
144         if(tmp)
145         {
146             sort(a+1,a+no);
147             printf("web %d:",i);
148             for(int j = 1;j < no;j++)
149                 printf(" %d",a[j]);
150             printf("
");
151             total++;
152         }
153     }
154     printf("total: %d
",total);
155     fclose(stdin);
156     // fclose(stdout);
157     return 0;
158 }