第一行，一個整數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;}新聞熱點
疑難解答
