病毒侵袭
- Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 37730 Accepted Submission(s): 8348
- Problem Description
当太阳的光辉逐渐被月亮遮蔽, 世界失去了光明, 大地迎来最黑暗的时刻.... 在这样的时刻, 人们却异常兴奋 -- 我们能在有生之年看到 500 年一遇的世界奇观, 那是多么幸福的事儿啊~~
但网路上总有那么些网站, 开始借着民众的好奇心, 打着介绍日食的旗号, 大肆传播病毒. 小 t 不幸成为受害者之一. 小 t 如此生气, 他决定要把世界上所有带病毒的网站都找出来. 当然, 谁都知道这是不可能的. 小 t 却执意要完成这不能的任务, 他说:"子子孙孙无穷匮也!"(愚公后继有人了).
万事开头难, 小 t 收集了好多病毒的特征码, 又收集了一批诡异网站的源码, 他想知道这些网站中哪些是有病毒的, 又是带了怎样的病毒呢? 顺便还想知道他到底收集了多少带病毒的网站. 这时候他却不知道何从下手了. 所以想请大家帮帮忙. 小 t 又是个急性子哦, 所以解决问题越快越好哦~~
Input
第一行, 一个整数 N(1<=N<=500), 表示病毒特征码的个数.
接下来 N 行, 每行表示一个病毒特征码, 特征码字符串长度在 20-200 之间.
每个病毒都有一个编号, 依此为 1-N.
不同编号的病毒特征码不会相同.
在这之后一行, 有一个整数 M(1<=M<=1000), 表示网站数.
接下来 M 行, 每行表示一个网站源码, 源码字符串长度在 7000-10000 之间.
每个网站都有一个编号, 依此为 1-M.
以上字符串中字符都是 ASCII 码可见字符 (不包括回车).
Output
依次按如下格式输出按网站编号从小到大输出, 带病毒的网站编号和包含病毒编号, 每行一个含毒网站信息.
web 网站编号: 病毒编号 病毒编号 ...
冒号后有一个空格, 病毒编号按从小到大排列, 两个病毒编号之间用一个空格隔开, 如果一个网站包含病毒, 病毒数不会超过 3 个.
最后一行输出统计信息, 如下格式
total: 带病毒网站数
冒号后有一个空格.
- Sample Input
- 3 aaa bbb ccc 2 aaabbbccc bbaacc
- Sample Output
- Web 1: 1 2 3 total: 1
- Source
- 2009 Multi-University Training Contest 10 - Host by NIT
- Recommend
- gaojie | We have carefully selected several similar problems for you: http://acm.hdu.edu.cn/showproblem.php?pid=3065 http://acm.hdu.edu.cn/showproblem.php?pid=2243 http://acm.hdu.edu.cn/showproblem.php?pid=2825 http://acm.hdu.edu.cn/showproblem.php?pid=3341 http://acm.hdu.edu.cn/showproblem.php?pid=3247
题意:
给定 n 个模式串, m 个文本串. 问每个文本串中有多少个模式串出现过, 输出他们的编号. 最后输出所有含有模式串的文本串个数.
思路:
暴力跑 AC 自动机. 有一些坑点.
第一是没看到说字符是 ASC 码中的字符, 刚开始就开了 26. 看题解说开 256 会 MLE, 开 130 左右就够了.
第二是对每个文本串进行统计时, 用了一个 vis 数组. 每一次查询一个文本串, vis 应该要重新初始化.
第三是输入的字符串中会有空格, 要用 gets
AC 自动机的题目一定要注意对每个节点进行初始化, 细节方面要考虑好.
好像今天有点浮躁, 写题目很草率啊.
- #include <iostream>
- #include <set>
- #include <cmath>
- #include <stdio.h>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <map>
- //#include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- #define inf 0x7f7f7f7f
- int m, n;
- const int maxn = 555;
- const int maxlen = 500 * 200 + 50;
- struct tree{
- int fail;
- int son[130];
- int ed;
- bool vis;
- }AC[maxlen];
- int tot = 0;
- char s[maxlen];
- void build(char s[], int id)
- {
- int len = strlen(s);
- int now = 0;
- for(int i = 0; i <len; i++){
- if(AC[now].son[s[i]] == 0){
- AC[now].son[s[i]] = ++tot;
- }
- now = AC[now].son[s[i]];
- }
- AC[now].ed = id;
- }
- void get_fail()
- {
- queue<int>que;
- for(int i = 0; i <130; i++){
- if(AC[0].son[i] != 0){
- AC[AC[0].son[i]].fail = 0;
- que.push(AC[0].son[i]);
- }
- }
- while(!que.empty()){
- int u = que.front();
- que.pop();
- for(int i = 0; i < 130; i++){
- if(AC[u].son[i] != 0){
- AC[AC[u].son[i]].fail = AC[AC[u].fail].son[i];
- que.push(AC[u].son[i]);
- }
- else{
- AC[u].son[i] = AC[AC[u].fail].son[i];
- }
- }
- }
- }
- int ans[5], top = 0;
- int AC_query(char s[])
- {
- for(int i = 0; i <= tot; i++){
- AC[i].vis = false;
- }
- int len = strlen(s);
- int now = 0, cnt = 0;
- for(int i = 0; i < len; i++){
- now = AC[now].son[s[i]];
- for(int t = now; t; t = AC[t].fail){
- if(!AC[t].vis && AC[t].ed != 0){
- ans[top] = AC[t].ed;
- //cout<<ans[top]<<endl;
- top++;
- cnt++;
- AC[t].vis = true;
- if(cnt>= 3)return cnt;
- }
- }
- }
- return cnt;
- }
- int main()
- {
- while(scanf("%d", &n) != EOF){
- for(int i = 0; i <= tot; i++){
- AC[i].ed = 0;
- AC[i].fail = 0;
- AC[i].vis = false;
- for(int j = 0; j < 130; j++){
- AC[i].son[j] = 0;
- }
- }
- tot = 0;
- for(int i = 1; i <= n; i++){
- getchar();
- gets(s);
- build(s, i);
- }
- AC[0].fail = 0;
- get_fail();
- scanf("%d", &m);
- int num = 0;
- for(int i = 1; i <= m; i++){
- getchar();
- gets(s);
- top = 0;
- if(AC_query(s)){
- printf("web %d:", i);
- sort(ans, ans + top);
- for(int j = 0; j < top; j++){
- printf("%d", ans[j]);
- }
- printf("\n");
- num++;
- }
- }
- printf("total: %d\n", num);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2831383.html