[題解]HDU2896病毒侵襲、HDU3065病毒侵襲持續中

2019-11-06 06:14:04

字體：大中小

來源：轉載

供稿：網友

HDU2896病毒侵襲

當太陽的光輝逐漸被月亮遮蔽，世界失去了光明，大地迎來最黑暗的時刻。。。。在這樣的時刻，人們卻異常興奮――我們能在有生之年看到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

3aaabbbccc2aaabbbcccbbaacc

Sample Output

web 1: 1 2 3total: 1

HDU3065病毒侵襲持續中

小t非常感謝大家幫忙解決了他的上一個問題。然而病毒侵襲持續中。在小t的不懈努力下，他發現了網路中的“萬惡之源”。這是一個龐大的病毒網站，他有著好多好多的病毒，但是這個網站包含的病毒很奇怪，這些病毒的特征碼很短，而且只包含“英文大寫字符”。當然小t好想好想為民除害，但是小t從來不打沒有準備的戰爭。知己知彼，百戰不殆，小t首先要做的是知道這個病毒網站特征：包含多少不同的病毒，每種病毒出現了多少次。大家能再幫幫他嗎？

Input

第一行，一個整數N（1<=N<=1000），表示病毒特征碼的個數。接下來N行，每行表示一個病毒特征碼，特征碼字符串長度在1―50之間，并且只包含“英文大寫字符”。任意兩個病毒特征碼，不會完全相同。在這之后一行，表示“萬惡之源”網站源碼，源碼字符串長度在2000000之內。字符串中字符都是ASCII碼可見字符（不包括回車）。

Output

按以下格式每行一個，輸出每個病毒出現次數。未出現的病毒不需要輸出。病毒特征碼: 出現次數冒號后有一個空格，按病毒特征碼的輸入順序進行輸出。

Sample Input

3AABBCCooxxCC%dAAAoen....END

Sample Output

AA: 2CC: 1

HINT

題目描述中沒有被提及的所有情況都應該進行考慮。比如兩個病毒特征碼可能有相互包含或者有重疊的特征碼段。計數策略也可一定程度上從Sample中推測。

Solution

這兩道題都是AC自動機的模板題。第二題比第一題只是要多了一個出現次數，這個很簡單，開個數組記錄就可以了。但是第二題有坑點。一開始我我看了HINT以為要考慮兩個病毒互相包含的情況，就像這個樣例：

2AABABABAABBAABABA

我以為應該輸出：

AABAB: 1ABA: 2

然后怎么都不對。。。后面拿別人的標程看看結果發現應該輸出：

AABAB: 1ABA: 1

我說這個HINT不是害人嗎？然后改完了交上去。。。繼續WA。。。我不甘心地拿別人的標程和我自己的對拍，用的是我自己生成的隨機數據，拍了1000多組都沒錯。我就納悶了，結果后來看看別人的程序打的都是多組數據打法，就是一個while(scanf("%d",&n)!=EOF),然后我無語的想這題不會有多組數據吧？結果改成多組數據就AC了。我真的是無話可說。。。多組數據題目里也不講一下。。。

代碼：

//HDU2896病毒侵襲#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=505,maxm=100010;struct node{ int next[128],fail,flag;}T[maxm];int n,m,num=1,tot,que[maxm],head,tail;char ch[maxm];bool exist[maxn];void Insert(char *s,int x){ int p=1,len=strlen(s); for(int i=0;i<len;i++){ if(!T[p].next[s[i]])T[p].next[s[i]]=++num; p=T[p].next[s[i]]; } T[p].flag=x;}void Bfs(){ memset(que,head=tail=0,sizeof que); que[++tail]=1; while(head<tail){ int x=que[++head]; for(int i=0;i<128;i++){ if(T[x].next[i]){ int p=T[x].fail; while(!T[p].next[i])p=T[p].fail; T[T[x].next[i]].fail=T[p].next[i]; que[++tail]=T[x].next[i]; } } }}bool Find(char *s){ memset(exist,0,sizeof exist); int p=1,len=strlen(s);bool f=false; for(int i=0;i<len;i++){ while(p&&!T[p].next[s[i]])p=T[p].fail; p=T[p].next[s[i]]; int temp=p; while(temp&&T[temp].flag){ exist[T[temp].flag]=true; f=true; temp=T[temp].fail; } } return f;}int main(){ for(int i=0;i<128;i++){ T[0].next[i]=1; } scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("/n%s",ch); Insert(ch,i); } scanf("%d",&m);Bfs(); for(int i=1;i<=m;i++){ scanf("/n%s",ch); if(Find(ch)){ tot++;