第一行，一个整数N（1<=N<=500），表示病毒特征码的个数。 接下来N行，每行表示一个病毒特征码，特征码字符串长度在20—200之间。 每个病毒都有一个编号，依此为1—N。 不同编号的病毒特征码不会相同。 在这之后一行，有一个整数M（1<=M<=1000），表示网站数。 接下来M行，每行表示一个网站源码，源码字符串长度在7000—10000之间。 每个网站都有一个编号，依此为1—M。 以上字符串中字符都是ASCII码可见字符（不包括回车）。
依次按如下格式输出按网站编号从小到大输出，带病毒的网站编号和包含病毒编号，每行一个含毒网站信息。 web 网站编号: 病毒编号 病毒编号 … 冒号后有一个空格，病毒编号按从小到大排列，两个病毒编号之间用一个空格隔开，如果一个网站包含病毒，病毒数不会超过3个。 最后一行输出统计信息，如下格式 total: 带病毒网站数 冒号后有一个空格。
3 aaa bbb ccc 2 aaabbbccc bbaacc
web 1: 1 2 3 total: 1
裸题，直接AC自动机即可。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int max_size = 200*501, ch_size = 130, M = 10000 + 10, N = 500 + 10;char s[M];int n, m;int sum;struct Trie{ int c[max_size][ch_size]; int val[max_size], f[max_size], last[max_size]; int sz; int ans[N]; bool ok; Trie() {sz = 1;} int idx(char c) {return (int)c;} void insert(char *s, int v){ int u = 0, n = strlen(s); for(int i = 0; i < n; i++){ int x = idx(s[i]); if(!c[u][x]){ c[u][x] = sz++; val[sz] = 0; } u = c[u][x]; } val[u] = v; } void get_fail(){ queue<int> q; f[0] = 0; for(int i = 0; i < ch_size; i++){ int u = c[0][i]; if(u){ f[u] = 0; q.push(u); last[u] = 0; } } while(!q.empty()){ int r = q.front(); q.pop(); for(int i = 0; i < ch_size; i++){ int u = c[r][i]; if(!u) {c[r][i] = c[f[r]][i]; continue;} q.push(u); int v = f[r]; while(v && !c[v][i]) v = f[v]; f[u] = c[v][i]; last[u] = val[f[u]] ? f[u] : last[f[u]]; } } } void PRint(int j){ ok = 1; //printf("%d %d/n", j, val[j]); if(j){ ans[val[j]] = 1; print(last[j]); } } void match(char *s){ int len = strlen(s), j = 0; for(int i = 0; i < len; i++){ int ch = idx(s[i]); j = c[j][ch]; if(val[j]) print(j); else if(val[last[j]]) print(last[j]); } }}t;void init(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%s", s); t.insert(s, i); } t.get_fail();}void work(){ scanf("%d", &m); for(int i = 1; i <= m; i++){ scanf("%s", s); memset(t.ans, 0, sizeof(t.ans)); t.ok = 0; t.match(s); if(t.ok){ sum++; printf("web %d:", i); for(int j = 1; j <= n; j++) if(t.ans[j]) printf(" %d", j); puts(""); } } printf("total: %d/n", sum);}int main(){ freopen("virus.in", "r", stdin); freopen("virus.out", "w", stdout); init(); work(); return 0;}新闻热点
疑难解答
