本文主要是介绍hdu 3056 病毒侵袭持续中 AC自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3065
刘汝佳的模板真的很好用，这道题直接过
学到：
cnt数组记录单词出现次数
以及map存储单词编号与字符串，便于处理相关信息
上代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;const int SIGMA_SIZE=128;
const int MAXNODE = 1005*55;
const int SSIZE = 2000000+100;struct AC
{int f[MAXNODE];int ch[MAXNODE][SIGMA_SIZE];int cnt[MAXNODE];int val[MAXNODE];int last[MAXNODE];int sz;void init(){memset(cnt,0,sizeof(cnt));memset(ch[0],0,sizeof(ch[0]));sz=1;f[0]=last[0]=val[0]=0;}inline void clear(){memset(cnt,0,sizeof(cnt));}void insert(string s,int v){int u=0,n=s.size();for(int i=0;i<n;i++){int c=s[i];if(!ch[u][c]){val[sz]=0;memset(ch[sz],0,sizeof(ch[sz]));ch[u][c]=sz++;}u=ch[u][c];}val[u]=v;}void print(int j){if(j){cnt[val[j]]++;print(last[j]);}}void getfail(){queue<int>q;for(int c=0;c<SIGMA_SIZE;c++){int u=ch[0][c];if(u){f[u]=0;q.push(u);last[u]=0;}}while(!q.empty()){int r=q.front();q.pop();for(int c=0;c<SIGMA_SIZE;c++){int u=ch[r][c];if(!u)continue;q.push(u);int v=f[r];while(v && !ch[v][c])v=f[v];f[u]=ch[v][c];last[u]=val[f[u]]?f[u]:last[f[u]];}}}void find(char *T){int n=strlen(T);int j=0;for(int i=0;i<n;i++){int c = T[i];while(j && !ch[j][c])j=f[j];j=ch[j][c];if(val[j])print(j);elseif(last[j])print(last[j]);}}
};AC ac;
char str[SSIZE];
int main()
{//freopen("hdu3056.txt","r",stdin);int n;string word;while(~scanf("%d",&n)){ac.init();map<int, string> ms;for(int i=1;i<=n;i++){cin >> word;ms[i]=word;ac.insert(word,i);}ac.getfail();scanf("%s",str);ac.find(str);for(int i=1;i<=n;i++){//printf("%d %d\n",i,ac.cnt[i]);///if(ac.cnt[i]){cout << ms[i] << ": " << ac.cnt[i] << endl;}}}return 0;
}
这篇关于hdu 3056 病毒侵袭持续中 AC自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
