本文主要是介绍HDU 3065 AC 自动机再来。。 病毒持续侵袭中，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
跟上一道题一样呀。。
代码不怎么用修改就能过啊。。
不过这次一个可能的优化是 病毒只有 A～Z 字符串是可见的 ASCII 码 遇到除了 A～Z 的指针 cur 直接回到 root 就可以了
。。。我注释掉了也没什么事情发生。。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <fstream>
#include <set>
#include <stack>
using namespace std;#define READ freopen("acm.in","r",stdin)
#define WRITE freopen("acm.out","w",stdout)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define MII map<int,int>::iterator
#define fst first
#define sec second
#define MS(x,d) memset(x,d,sizeof(x))
#define INF 0x3f3f3f3f
#define ALL(x) x.begin(),x.end()
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ROOT 0,n-1,1
#define PB push_back
#define FOR(a,b,c) for(int a=b;a<c;a++)
#define MOD 1000000007
#define keyTree (ch[ ch[root][1] ][0])
#define MAX 200
#define SIG 128
struct Node
{Node* next[SIG];Node* fail;int flag;Node(){MS(next,0);fail=NULL;flag=0;}
};
char vir[1111][50];
char text[2000100];
struct ACAutomaton
{Node* root;void Init(){root=new Node;}void del(Node* p){for(int i=0;i<SIG;i++)if(p->next[i])del(p->next[i]);delete p;}void Insert(char *c,int key){Node* p=root;for(int i=0;c[i];i++){int id=c[i];if(p->next[id]==NULL)p->next[id]=new Node;p=p->next[id];} p->flag=key;}void Construct(){queue<Node*> q;for(int i=0;i<SIG;i++){if(root->next[i]!=NULL){root->next[i]->fail=root;q.push(root->next[i]);}}while(!q.empty()){Node* u=q.front();q.pop();for(int i=0;i<SIG;i++){Node* v=u->next[i];if(v!=NULL){q.push(v);Node* p=u->fail;while(p!=root&&p->next[i]==NULL)p=p->fail;v->fail=p->next[i]==NULL?root:p->next[i];}}}}void solve(char *s){int ans[2200];MS(ans,0);Node* cur=root;for(int i=0;s[i];i++){/*if(s[i]<'A'||s[i]>'Z'){cur=root;continue;}*/int id=s[i];while(cur!=root&&cur->next[id]==NULL)cur=cur->fail;cur=cur->next[id]?cur->next[id]:root;for(Node* p=cur;p!=root&&p->flag;p=p->fail)ans[p->flag]+=1;}for(int i=1;i<2100;i++){if(ans[i]){printf("%s: %d\n",vir[i],ans[i]);}}}
}AC;
int main()
{READ;int n;while(scanf("%d",&n)!=EOF){AC.Init();for(int i=1;i<=n;i++){scanf("%s",vir[i]);AC.Insert(vir[i],i);}int m;AC.Construct();scanf("%d",&m);scanf("%s",text);AC.solve(text);AC.del(AC.root);} return 0;
}这篇关于HDU 3065 AC 自动机再来。。 病毒持续侵袭中的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
