首页 > 代码库 > HDU 2896 病毒侵袭(AC自动机)
HDU 2896 病毒侵袭(AC自动机)
题目:戳这里
题意:求m个网站出现过的病毒串并按id从小到大输出。最后一行输出含有病毒的网站数量。
思路:AC自动机模板题,注意可见字符的范围是128...这题空间卡的比较严。。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> using namespace std; const int maxw = 130; const int maxn = 210; const int time = 505; const int maxs = 10010; struct DFAAC{ int tire[maxn*time][maxw]; int fail[maxn*time]; int tag[maxn*time]; bool vis[time]; int P , root , tail , stat; int New(){ tail = stat = 0; for(int i=0;i<maxw;i++) tire[P][i] = -1;tag[P] = 0; return P++; } void init(){ P=0;root =New(); } void Insert(char ch[] , int id){ int now = root; for(int i=0;ch[i];i++){ if(tire[now][ch[i]]==-1) tire[now][ch[i]] = New(); now = tire[now][ch[i]]; } tag[now] = id; } void built() { queue<int>Q; fail[root] = root; for(int i = 0 ; i < maxw;i++){ if(tire[root][i]!=-1){ Q.push(tire[root][i]); fail[tire[root][i]] = root; } else tire[root][i] = root; } while(!Q.empty()){ int u = Q.front();Q.pop(); for(int i=0;i < maxw;i++){ if(tire[u][i]!=-1){ fail[tire[u][i]] = tire[fail[u]][i]; Q.push(tire[u][i]); } else tire[u][i] = tire[fail[u]][i]; } } } void Match(char ch[]){ memset(vis,0,sizeof(vis)); int now = root; for(int i=0;ch[i];i++){ now = tire[now][ch[i]]; int tmp = now; while(tmp!=root){ if(tag[tmp]) vis[tag[tmp]] = 1; tmp = fail[tmp]; } } } }; DFAAC ac; char ch[maxs]; int n , m; vector<int>ans[maxs]; int main() { while(~scanf("%d",&n)){ ac.init(); for(int i=1;i<=n;i++){ scanf("%s",ch); ac.Insert(ch , i); } ac.built(); scanf("%d",&m); for(int i=1;i<=m;i++) ans[i].clear(); for(int i=1;i<=m;i++){ memset(ac.vis,0,sizeof(ac.vis)); scanf("%s",ch); ac.Match(ch); for(int j=1;j<=n;j++){ if(ac.vis[j]){ ans[i].push_back(j); } } } int tot = 0; for(int i=1;i<=m;i++){ int sz = ans[i].size(); if(sz!=0)printf("web %d:",i),tot++; for(int j = 0 ; j < sz;j++){ printf(" %d",ans[i][j]); } if(sz!=0) printf("\n"); } printf("total: %d\n",tot); } }
HDU 2896 病毒侵袭(AC自动机)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。