HDU3065病毒侵袭持续中(AC自动机)

描述

传送门:我是传送门

小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下,他发现了网路中的“万恶之源”。这是一个庞大的病毒网站,他有着好多好多的病毒,但是这个网站包含的病毒很奇怪,这些病毒的特征码很短,而且只包含“英文大写字符”。当然小t好想好想为民除害,但是小t从来不打没有准备的战争。知己知彼,百战不殆,小t首先要做的是知道这个病毒网站特征:包含多少不同的病毒,每种病毒出现了多少次。大家能再帮帮他吗?

输入

第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。
接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。
在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

输出

按以下格式每行一个,输出每个病毒出现次数。未出现的病毒不需要输出。
病毒特征码: 出现次数
冒号后有一个空格,按病毒特征码的输入顺序进行输出。

样例

输入

3
AA
BB
CC
ooxxCC%dAAAoen….END

输出

AA: 2
CC: 1

Note

题目描述中没有被提及的所有情况都应该进行考虑。比如两个病毒特征码可能有相互包含或者有重叠的特征码段。
计数策略也可一定程度上从Sample中推测。

思路

病毒侵袭实际上差不太多,也不知道我当时为什么写完病毒侵袭之后看了看这道题就放弃了。

一开始很奇怪的RE了无数次,也不知道哪里写搓了,正在要绝望的时候突然AC了···

代码

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
159
160
161
162
163
164
165
166
167
/*
* ==============================================
*
* Filename: C.cpp
*
* Link: http://acm.hdu.edu.cn/showproblem.php?pid=3065
*
* Version: 1.0
* Created: 2018/09/26 23时12分29秒
* 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=n;i>=a;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 = 1005;
const int NN = 2001000;
char m[NN];
char vir[N][55];
int a[N];
struct node
{
int son[27];
int fail;
int count;
int number;
}ac[100*N];
int tot = 0;
void init()
{
clr(a,0);
for(int i = 0;i < 50000;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]-'A';
if(ac[now].son[tmp] == 0)
ac[now].son[tmp] = ++tot;
now = ac[now].son[tmp];
}
ac[now].count++;
ac[now].number = num;
}

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

void MakeFail()
{
queue<int> q;
for(int i = 0;i < 26;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 < 26;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];
}
}
}

void query(char *s)
{
int len = strlen(s);
int now = 0,tmp;
for(int i = 0;i < len;i++)
{
tmp = s[i]-'A';
if(tmp < 0 || tmp > 25)
tmp = 26;
now = ac[now].son[tmp];
for(int t = now;t && ac[t].count != -1;t = ac[t].fail)
{
if(ac[t].number > 0)
{
a[ac[t].number]++;
}
// ans += ac[t].count;
// ac[t].count = -1;
}
}
// return ans;
}

int main()
{
ios
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
int n;
while(scanf("%d",&n) != EOF)
{
init();
rep(i,1,n)
{
scanf("%s",vir[i]);
Insert1(vir[i],i);
}
ac[0].fail = 0;
MakeFail();
scanf("%s",m);
query(m);
rep(i,1,n)
{
if(a[i])
printf("%s: %d\n",vir[i],a[i]);
}
}
fclose(stdin);
// fclose(stdout);
return 0;
}