HDU 3695 Computer Virus on Planet Pandora and HDU 2896 病毒侵袭(AC自动机裸题)

本文主要是介绍HDU 3695 Computer Virus on Planet Pandora and HDU 2896 病毒侵袭(AC自动机裸题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

都是给出几个病毒模式串，然后再给一个串看其中有多少个病毒，不同的是3695要求将串反转一次，2896是对于每个网站按照标号顺序输出含有的病毒串和含有病毒的网站总数。

解题思路

都是按照给的病毒模式串建立AC自动机，3695将串正向和反向均匹配一次，2896是将记录每个匹配到的字符串然后按照标号顺序输出，注意要对已经匹配到的病毒串进行标记，避免重复计数。
另外我的代码G++MLE，C++AC。初涉AC自动机，解决办法还未知……

代码实现

HDU 3695 Computer Virus on Planet Pandora

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdlib.h>
#include<cstdio>
using namespace std;
#define maxn 5100100
char S[maxn],s[maxn];
bool visit[257];
int num,cnt;
//字典树节点结构体
struct node
{node *next[26];node *fail;int id;node(){id=-1;memset(next,0,sizeof(next));fail=NULL;}
};
node *root,*newnode;
//字典树建立
void Insert(char *s,int id)
{node *p = root;int len=strlen(s);for(int i = 0; i<len; i++){int x = s[i] - 'A';if(p->next[x]==NULL)p->next[x]=new node();p=p->next[x];}p->id=id;
}
//构造fail指针
void build_fail_pointer()
{queue<node *>qu;node *ans;node *temp;while(!qu.empty()) qu.pop();qu.push(root);while(!qu.empty()){temp=qu.front();qu.pop();for(int i = 0; i < 26; i++){if(temp->next[i]){if(temp == root){temp->next[i]->fail = root;}else{ans = temp->fail;while(ans){if(ans->next[i]){temp->next[i]->fail = ans->next[i];break;}ans = ans->fail;}if(ans == NULL)temp->next[i]->fail = root;}qu.push(temp->next[i]);}}}
}
//进行匹配
int ac_automation(char *s)
{cnt = 0;node *p = root;node *temp;int len=strlen(s);for(int i = 0; i < len; i++){int x = s[i] - 'A';while(p&&p->next[x] == NULL)p = p->fail;if(p == NULL)p = root;p = p->next[x];if(p){temp = p;while(temp&&temp->id != -1&&!visit[temp->id]){visit[temp->id] = true;cnt++;temp = temp->fail;}}}return cnt;
}
int main()
{int T,n,ans;scanf("%d%*c",&T);while(T--){memset(visit,0,sizeof(visit));ans=0;scanf("%d%*c",&n);num=0;root = new node();for(int i=1; i<=n; i++){scanf("%s",S);Insert(S,i);}build_fail_pointer();scanf("%s",s);memset(S,0,sizeof(S));int j=0,k=0,t=0;int length=strlen(s);//将压缩字符串解压while(j<length){if(s[j]=='['){t=0;j++;while(s[j]>='0'&&s[j]<='9'&&j<length){t=(t*10+s[j]-'0');j++;}for(int l=0; l<t; l++)S[k++]=s[j];j+=2;}else if(s[j]>='A'&&s[j]<='Z')S[k++]=s[j++];}S[k]='\0';ans+=ac_automation(S);reverse(S,S+strlen(S));ans+=ac_automation(S);printf("%d\n",ans);}return 0;
}

HDU 2896 病毒侵袭

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdlib.h>
#include<cstdio>
using namespace std;
#define maxn 10007
#define maxx 507
char S[10010];
int result[507];
bool visit[507];
int num,cnt;
//字典树节点结构体
struct node
{node *next[100];node *fail;int id;node(){id=0;memset(next,0,sizeof(next));fail=NULL;}
}*root,*newnode;
//建立字典树
void Insert(char *s,int id)
{node *p = root;int len=strlen(s);for(int i = 0; i<len; i++){int x = s[i] - ' ';if(p->next[x] == NULL)p->next[x]=new node();p = p->next[x];}p->id=id;
}
//构造fail指针
void build_fail_pointer()
{queue<node *>qu;node *ans;node *temp;while(!qu.empty()) qu.pop();qu.push(root);while(!qu.empty()){temp=qu.front();qu.pop();for(int i = 0; i < 100; i++){if(temp->next[i]){if(temp == root){temp->next[i]->fail = root;}else{ans = temp->fail;while(ans){if(ans->next[i]){temp->next[i]->fail = ans->next[i];break;}ans = ans->fail;}if(ans == NULL) temp->next[i]->fail = root;}qu.push(temp->next[i]);}}}
}
//进行匹配求解
int ac_automation(char *s)
{cnt = 0;node *p = root;node *temp;int len=strlen(s);for(int i = 0; i < len; i++){int x = s[i] - ' ';while(p&&p->next[x] == NULL) p = p->fail;if(p == NULL) p = root;p = p->next[x];if(p){temp = p;while(temp){if(temp->id != 0){if(!visit[temp->id]){visit[temp->id] = true;cnt++;result[cnt]=temp->id;}}temp = temp->fail;}}}return cnt;
}
int main()
{int n,m,ans;while(~scanf("%d%*c",&n)){ans=0;num=0;root=new node();for(int i=1; i<=n; i++){scanf("%s",S);Insert(S,i);}build_fail_pointer();scanf("%d",&m);for(int i=1; i<=m; i++){memset(visit,0,sizeof(visit));scanf("%s",S);int x=ac_automation(S);if(x!=0){ans++;sort(result+1,result+x+1);printf("web %d:",i);for(int j=1; j<=x; j++)printf(" %d",result[j]);printf("\n");}}printf("total: %d\n",ans);}return 0;
}