本文主要是介绍HDU 2896 病毒传播 AC 自动机 蛮裸的。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
还是喜欢指针版本的数据结构(Splay 啦 AC 自动机啦)
首先给病毒串建立 AC 自动机，然后判断病毒串在文本中的存在情况就是了。
#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;}
};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];}}}}bool solve(char *s,int n){int ans[502];MS(ans,0);Node* cur=root;for(int i=0;s[i];i++){int id=s[i];while(cur!=root&&cur->next[id]==NULL)cur=cur->fail;cur=cur->next[id]?cur->next[id]:root;// Notice 别忘了更新 cur ORZfor(Node* p=cur;p!=root&&p->flag;p=p->fail)ans[p->flag]=1;}int cnt=0;for(int i=0;i<=500;i++){if(ans[i])cnt++;}if(cnt>0){printf("web %d:",n);for(int i=0;i<=501;i++)if(ans[i])cout<<" "<<i;cout<<endl;return true;}return false;}
}AC;
char vir[2000];
char text[20000];
int main()
{READ;int n;while(scanf("%d",&n)!=EOF){AC.Init();for(int i=1;i<=n;i++){scanf("%s",vir);AC.Insert(vir,i);}int m;AC.Construct();scanf("%d",&m);int ans=0;for(int i=1;i<=m;i++){scanf("%s",text);ans+=AC.solve(text,i);}AC.del(AC.root);printf("total: %d\n",ans);} return 0;
}这篇关于HDU 2896 病毒传播 AC 自动机 蛮裸的。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
