hdu2896 病毒侵襲

2019-11-09 20:01:31

字體：大中小

供稿：網(wǎng)友

hdu 2896

Description

當(dāng)太陽的光輝逐漸被月亮遮蔽，世界失去了光明，大地迎來最黑暗的時(shí)刻。。。。在這樣的時(shí)刻，人們卻異常興奮——我們能在有生之年看到500年一遇的世界奇觀，那是多么幸福的事兒啊~~但網(wǎng)路上總有那么些網(wǎng)站，開始借著民眾的好奇心，打著介紹日食的旗號(hào)，大肆傳播病毒。小t不幸成為受害者之一。小t如此生氣，他決定要把世界上所有帶病毒的網(wǎng)站都找出來。當(dāng)然，誰都知道這是不可能的。小t卻執(zhí)意要完成這不能的任務(wù)，他說：“子子孫孫無窮匱也！”（愚公后繼有人了）。萬事開頭難，小t收集了好多病毒的特征碼，又收集了一批詭異網(wǎng)站的源碼，他想知道這些網(wǎng)站中哪些是有病毒的，又是帶了怎樣的病毒呢？順便還想知道他到底收集了多少帶病毒的網(wǎng)站。這時(shí)候他卻不知道何從下手了。所以想請(qǐng)大家?guī)蛶兔ΑＰ又是個(gè)急性子哦，所以解決問題越快越好哦~~

Input

第一行，一個(gè)整數(shù)N（1<=N<=500），表示病毒特征碼的個(gè)數(shù)。接下來N行，每行表示一個(gè)病毒特征碼，特征碼字符串長度在20—200之間。每個(gè)病毒都有一個(gè)編號(hào)，依此為1—N。不同編號(hào)的病毒特征碼不會(huì)相同。在這之后一行，有一個(gè)整數(shù)M（1<=M<=1000），表示網(wǎng)站數(shù)。接下來M行，每行表示一個(gè)網(wǎng)站源碼，源碼字符串長度在7000—10000之間。每個(gè)網(wǎng)站都有一個(gè)編號(hào)，依此為1—M。以上字符串中字符都是ASCII碼可見字符（不包括回車）。

Output

依次按如下格式輸出按網(wǎng)站編號(hào)從小到大輸出，帶病毒的網(wǎng)站編號(hào)和包含病毒編號(hào)，每行一個(gè)含毒網(wǎng)站信息。 web 網(wǎng)站編號(hào): 病毒編號(hào) 病毒編號(hào) … 冒號(hào)后有一個(gè)空格，病毒編號(hào)按從小到大排列，兩個(gè)病毒編號(hào)之間用一個(gè)空格隔開，如果一個(gè)網(wǎng)站包含病毒，病毒數(shù)不會(huì)超過3個(gè)。最后一行輸出統(tǒng)計(jì)信息，如下格式 total: 帶病毒網(wǎng)站數(shù) 冒號(hào)后有一個(gè)空格。

Sample Input

3 aaa bbb ccc 2 aaabbbccc bbaacc

Sample Output

web 1: 1 2 3 total: 1

題解

裸題，直接AC自動(dòng)機(jī)即可。

#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;}

上一篇：C#復(fù)選框

下一篇：poj2039