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
AC自动机变形体题，字典树插入的时候不仅仅要记录当前根节点结尾的单词数量还需要记住当前根节点结尾的是哪一个单词。然后正常的预处理失败指针。在查询的时候这里不能将单词数清空为0，为了不干扰后面的查询所以开一个vector容器，查到一个就记录一个单词编号，最后输出的时候排序去重。这道题有点坑，我开的6w * 134大小的数组，题解开的10 * 135w。我MLE，几乎一样的写法。各种报错，RE WA TLE MLE…最后AC的代码就剩下10k的内存差一点就超了。
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; const int maxn = 60005; vector<int>v; int trie[maxn][130]; int num[maxn],fail[maxn]; int cnt,s[maxn]; char p[10005]; void insert_s(int id) { int n = strlen(p); int root = 0; for(int i = 0;i < n;i++){ int k = (int)p[i]; if(!trie[root][k]){ trie[root][k] = ++cnt; } root = trie[root][k]; } num[root]++; s[root] = id; } void get_fail() { queue<int>q; for(int i = 0;i < 130;i++){ if(trie[0][i]){ fail[trie[0][i]] = 0; q.push(trie[0][i]); } } while(!q.empty()){ int root = q.front(); q.pop(); for(int i = 0;i < 130;i++){ if(trie[root][i]){ fail[trie[root][i]] = trie[fail[root]][i]; q.push(trie[root][i]); } else{ trie[root][i] = trie[fail[root]][i]; } } } return ; } void query() { int n = strlen(p); int root = 0,ans = 0; for(int i = 0;i < n;i++){ int k = (int)p[i]; root = trie[root][k]; for(int j = root;j && num[j];j = fail[j]){ v.push_back(s[j]); // num[j] = 0; } } } int main() { int n,m; scanf("%d",&n); memset(trie,0,sizeof(trie)); memset(num,0,sizeof(num)); memset(fail,0,sizeof(fail)); memset(s,0,sizeof(s)); cnt = 0; for(int i = 1;i <= n;i++){ scanf("%s",p); insert_s(i); } get_fail(); scanf("%d",&m); int sum = 0; for(int i = 1;i <= m;i++){ scanf("%s",p); v.clear(); query(); int ans = v.size(); if(ans == 0) continue; sum++; sort(v.begin(),v.end()); ans = unique(v.begin(),v.end()) - v.begin(); printf("web %d:",i); for(int j = 0;j < ans;j++){ printf(" %d",v[j]); } printf("\n"); } printf("total: %d\n",sum); return 0; }