生活随笔
收集整理的這篇文章主要介紹了
HDU2896(病毒侵袭--AC自动机)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目：病毒侵襲
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <queue>using namespace std;const int N=1000050;char S[N];
char keyword[256];class Trie
{public:int index;Trie *fail;Trie *next[128];Trie(){index=0;fail=NULL;memset(next,NULL,sizeof(next));}
};Trie *root;
queue<Trie*>Q;int ss[5500][5],k[5500];void Insert(char *S,int value)
{int len=strlen(S);Trie *p=root;for(int i=0; i<len; i++){int id=S[i]-' ';if(p->next[id]==NULL)p->next[id]=new Trie();p=p->next[id];}p->index=value;
}void Build_AC()
{Q.push(root);root->fail=NULL;while(!Q.empty()){Trie *p=NULL;Trie *tmp=Q.front();Q.pop();for(int i=0; i<128; i++){if(tmp->next[i]){if(tmp==root) tmp->next[i]->fail=root;else{p=tmp->fail;while(p){if(p->next[i]){tmp->next[i]->fail=p->next[i];break;}p=p->fail;}if(p==NULL) tmp->next[i]->fail=root;}Q.push(tmp->next[i]);}}}
}void Query(char *S,int c)
{Trie *p=root;int flag[550];k[c]=0;memset(flag,0,sizeof(flag));int index;int len=strlen(S);for(int i=0; i<len; i++){index=S[i]-' ';while(p->next[index]==NULL&&p!=root) p=p->fail;p=p->next[index];if(p==NULL) p=root;Trie *tmp=p;while(tmp!=root&&!flag[tmp->index]){if(tmp->index){ss[c][k[c]++]=tmp->index;flag[tmp->index]=1;}tmp=tmp->fail;}if(k[c]>=3) break;}
}int main()
{int t,n,m;while(~scanf("%d",&n)){root=new Trie();getchar();for(int i=1; i<=n; i++){gets(keyword);Insert(keyword,i);}Build_AC();scanf("%d",&m);int total=0;for(int i=1; i<=m; i++){scanf("%s",S);Query(S,i);if(k[i]){sort(ss[i],ss[i]+k[i]);total++;}}for(int i=1; i<=m; i++){if(!k[i]) continue;printf("web %d:",i);for(int j=0; j<k[i]; j++)printf(" %d",ss[i][j]);puts("");}printf("total: %d\n",total);}return 0;
}
總結
以上是生活随笔為你收集整理的HDU2896(病毒侵袭--AC自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
