当太阳的光辉逐渐被月亮遮蔽, 世界失去了光明, 大地迎来最黑暗的时刻.... 在这样的时刻, 人们却异常兴奋 -- 我们能在有生之年看到 500 年一遇的世界奇观, 那是多么幸福的事儿啊~~
但网路上总有那么些网站, 开始借着民众的好奇心, 打着介绍日食的旗号, 大 4 传播病毒. 小 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
- /**
- 完成时间: 2018.9.12
- 依言
- 算法: AC 自动机
- */
- #include<iostream>
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int SON=128;
- const int MAXN=200*500+50;
- struct AC_Auto
- {
- int root,L;
- int next[MAXN][SON];
- int fail[MAXN];
- int num[4];
- int number[MAXN];
- int New_Node()
- {
- for(int i=0;i <SON;++i)
- next[L][i]=-1;
- num[L]=0;
- return L++;
- }
- void Initial()
- {
- L=0;
- root=New_Node();
- }
- void Build_Trie(const char *s,const int id)
- {
- int now=root;
- while(*s != '\0')
- {
- int index=*s;
- if(next[now][index] == -1)
- next[now][index]=New_Node();
- now=next[now][index];
- s++;
- }
- num[now]=id;// 将结束字符赋值为病毒编号
- }
- void Build_Fail()
- {
- queue<int>myqueue;
- for(int i=0;i <SON;++i)
- if(next[root][i] == -1)
- next[root][i]=root;
- else
- {
- fail[next[root][i]]=root;
- myqueue.push(next[root][i]);
- }
- while(!myqueue.empty())
- {
- int now=myqueue.front();
- myqueue.pop();
- for(int i=0;i < SON;++i)
- if(next[now][i] == -1)
- next[now][i]=next[fail[now]][i];
- else
- {
- fail[next[now][i]]=next[fail[now]][i];
- myqueue.push(next[now][i]);
- }
- }
- }
- int Query(const char *s)
- {
- int cnt=0;
- int now=root;
- bool vis[MAXN];
- memset(vis,false,sizeof(vis));
- while(*s != '\0')
- {
- int index=*s;
- now=next[now][index];
- int temp=now;
- while(temp != root && num[temp] != 0 && !vis[num[temp]])
- {
- number[cnt++]=num[temp];
- temp=fail[temp];
- vis[num[temp]]=true;
- }
- s++;
- }
- return cnt;
- }
- };
- AC_Auto ac;
- char buf[10010];
- int main()
- {
- int N;
- scanf("%d",&N);
- ac.Initial();
- for(int i=1;i <= N;++i)
- {
- scanf("%s",buf);
- ac.Build_Trie(buf,i);
- }
- ac.Build_Fail();
- int M;
- scanf("%d",&M);
- int total=0;
- for(int i=1;i <= M;++i)
- {
- scanf("%s",buf);
- int cnt=ac.Query(buf);
- if(cnt> 0)
- {
- total++;
- sort(ac.number,ac.number+cnt);
- printf("web %d:",i);
- for(int i=0;i < cnt;++i)
- printf("%d",ac.number[i]);
- printf("\n");
- }
- }
- printf("total: %d\n",total);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2765343.html