HDU2896 病毒侵袭(AC自动机)

描述

传送门:我是传送门

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

输入

第一行,一个整数$N(1<=N<=500)$,表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在$20—200$之间。 每个病毒都有一个编号,依此为$1-N$。 不同编号的病毒特征码不会相同。 在这之后一行,有一个整数$M(1<=M<=1000)$,表示网站数。 接下来$M$行,每行表示一个网站源码,源码字符串长度在$7000—10000$之间。 每个网站都有一个编号,依此为$1—M$。 以上字符串中字符都是ASCII码可见字符(不包括回车)。

输出

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

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

total: 带病毒网站数

冒号后有一个空格。

样例

输入

3
aaa
bbb
ccc
2
aaabbbccc
bbaacc

输出

web 1: 1 2 3
total: 1

思路

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

但是有一些细节需要注意

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
* =========================================================================
*
* Filename: B.cpp
*
* Link: http://acm.hdu.edu.cn/showproblem.php?pid=2896
*
* Version: 1.0
* Created: 2018/09/02 11时45分16秒
* Revision: none
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* =========================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=a;i>=n;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6+100;
struct node
{
int son[128];
int fail;
int count;
int number;
}ac[N];
int tot = 0;
void init()
{
for(int i = 0;i < N;i++)
{
memset(ac[i].son,0,sizeof ac[i].son);
ac[i].count = 0;
ac[i].fail = 0;
ac[i].number = 0;
}
}

void Insert(char *s,int num)
{
int len = strlen(s);
int now = 0;
int tmp;
for(int i = 0;i < len;i++)
{
tmp = s[i];
if(ac[now].son[tmp] == 0)
ac[now].son[tmp] = ++tot;
now = ac[now].son[tmp];
}
ac[now].count++;
ac[now].number = num;
}

void MakeFail()
{
queue<int> q;
for(int i = 0;i < 128;i++)
{
if(ac[0].son[i] != 0)
{
ac[ac[0].son[i]].fail = 0;
q.push(ac[0].son[i]);
}
}
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0;i < 128;i++)
{
if(ac[u].son[i] != 0)
{
ac[ac[u].son[i]].fail = ac[ac[u].fail].son[i];
q.push(ac[u].son[i]);
}
else
ac[u].son[i] = ac[ac[u].fail].son[i];
}
}
}

int Query(char *s,int &no,int *a)
{
int len = strlen(s);
int now = 0,ans = 0,tmp;
for(int i = 0;i < len;i++)
{
tmp = s[i];
now = ac[now].son[tmp];
for(int t = now;t && ac[t].count != -1;t = ac[t].fail)
{
if(ac[t].number > 0)
{
a[no++] = ac[t].number;
}
ans += ac[t].count;
// 注意这里 不可以在查询后将count修改为-1
// 因为需要进行多次查询
// ac[t].count = -1;
}
}
return ans;
}
char s[210];
char Ts[10100];
int main()
{
ios
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
int N,M;
scanf("%d",&N);
for(int i = 1;i <= N;i++)
{
scanf("%s",s);
Insert(s,i);
}
ac[0].fail = 0;
MakeFail();
scanf("%d",&M);
int total = 0;
for(int i = 1;i <= M;i++)
{
int a[5];
clr(a,0);
int no = 1;
scanf("%s",Ts);
// printf("%s\n",Ts);
int tmp = Query(Ts,no,a);
if(tmp)
{
sort(a+1,a+no);
printf("web %d:",i);
for(int j = 1;j < no;j++)
printf(" %d",a[j]);
printf("\n");
total++;
}
}
printf("total: %d\n",total);
fclose(stdin);
// fclose(stdout);
return 0;
}