HDU - 2896 题目解答:当太阳的光辉逐渐被月亮遮蔽,世界失去了光明,大地迎来最黑暗的时刻。在这样的时刻,人们却异常兴奋――我们能在有生之年看到 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 Input3aaabbbccc2aaabbbcccbbaacc
Sample Outputweb 1: 1 2 3total: 1
思路:模式匹配:这类问题一般都是统计目标串中模式串的个数直接套板子
- #include#include#include#include#include#include#include#include#include#define LL long long using namespace std;
- const int maxn = 128;
- struct Trie {
- int next[210 * 500][maxn];
- int fail[210 * 500],
- end[210 * 500];
- int root,
- L;
- int newnode() //初始化 { for(int i=0;i<128;i++) next[L][i]=-1; end[L++]=-1; return L-1; } void init()//初始化 { L=0; root=newnode(); } void insert(char s[],int id)//构造数trie { int len=strlen(s); int now=root; for(int i=0;iQ; fail[root]=root; for(int i=0;i<128;i++) if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()) { int now=Q.front(); Q.pop(); for(int i=0;i<128;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } bool vis[510]; bool query(char buf[],int n,int id)//查询 { int len=strlen(buf); int now=root; memset(vis,0,sizeof(vis)); bool flag=false; for(int i=0;i
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/04-12/20351321.html