HDU 3065 病毒侵袭持续中 (AC自动机)
来源：程序员人生 发布时间：2015-03-17 08:54:42 阅读次数：2721次
病毒侵袭延续中
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7477 Accepted Submission(s): 2595
Problem Description
小t非常感谢大家帮忙解决了他的上1个问题。但是病毒侵袭延续中。在小t的不懈努力下，他发现了网路中的“万恶之源”。这是1个庞大的病毒网站，他有着好多好多的病毒，但是这个网站包括的病毒很奇怪，这些病毒的特点码很短，而且只包括“英文大写字符”。固然小t好想好想为民除害，但是小t历来不打没有准备的战争。知己知彼，百战百胜，小t首先要做的是知道这个病毒网站特点：包括多少不同的病毒，每种病毒出现了多少次。大家能再帮帮他吗？
Input
第1行，1个整数N（1<=N<=1000），表示病毒特点码的个数。
接下来N行，每行表示1个病毒特点码，特点码字符串长度在1―50之间，并且只包括“英文大写字符”。任意两个病毒特点码，不会完全相同。
在这以后1行，表示“万恶之源”网站源码，源码字符串长度在2000000以内。字符串中字符都是ASCII码可见字符（不包括回车）。
Output
按以下格式每行1个，输出每一个病毒出现次数。未出现的病毒不需要输出。
病毒特点码: 出现次数
冒号后有1个空格，按病毒特点码的输入顺序进行输出。
Sample Input
3
AA
BB
CC
ooxxCC%dAAAoen....END
Sample Output
AA: 2
CC: 1
Hint
Hit：
题目描写中没有被提及的所有情况都应当进行斟酌。比如两个病毒特点码可能有相互包括或有堆叠的特点码段。
计数策略也可1定程度上从Sample中推测。
Source
2009 Multi-University Training Contest 16
- Host by NIT
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3065
题目分析：裸的AC自动机，忽视了只含大写字母，MLE了，注意是多组数据，存1下每一个单词和对应的出现次数
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int const MAX = 2000005;
char word[1005][55], text[MAX];
int cnt[1005];
struct node
{
int id;
bool end;
node *next[26];
node *fail;
node()
{
id = ⑴;
end = false;
memset(next, NULL, sizeof(next));
fail = NULL;
}
};
void Insert(node *p, char *s, int id)
{
for(int i = 0; s[i] != ''; i++)
{
int idx = s[i] - 'A';
if(p -> next[idx] == NULL)
p -> next[idx] = new node();
p = p -> next[idx];
}
p -> end = true;
p -> id = id;
}
void AC_Automation(node *root)
{
queue <node*> q;
q.push(root);
while(!q.empty())
{
node *p = q.front();
q.pop();
for(int i = 0; i < 26; i++)
{
if(p -> next[i])
{
if(p == root)
p -> next[i] -> fail = root;
else
p -> next[i] -> fail = p -> fail -> next[i];
q.push(p -> next[i]);
}
else
{
if(p == root)
p -> next[i] = root;
else
p -> next[i] = p -> fail -> next[i];
}
}
}
}
bool Query(node *root)
{
bool flag = false;
int len = strlen(text);
node *p = root;
for(int i = 0; i < len; i++)
{
int idx = text[i] - 'A';
if(idx < 0 || idx > 25)
{
p = root;
continue;
}
while(!p -> next[idx] && p != root)
p = p -> fail;
p = p -> next[idx];
if(!p)
{
p = root;
continue;
}
node *tmp = p;
while(tmp != root)
{
if(tmp -> end)
{
flag = true;
cnt[tmp -> id]++;
}
else
break;
tmp = tmp -> fail;
}
}
return flag;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
memset(cnt, 0, sizeof(cnt));
node *root = new node();
for(int i = 0; i < n; i++)
{
scanf("%s", word[i]);
Insert(root, word[i], i);
}
AC_Automation(root);
getchar();
gets(text);
if(Query(root))
for(int i = 0; i < n; i++)
if(cnt[i])
printf("%s: %d
", word[i], cnt[i]);
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
