本文主要是介绍HDU 3065病毒侵袭持续中 AC自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意很明了，就是找每个匹配串在文本中出现的次数，并且根据题意可以可以有重复部分。
所以这个题与板子不同的地方就是查找的一部分。
还有就是多组输入！！！
/*┆ ┏┓ ┏┓ ┆┆┏┛┻━━━━━━┛┻┓ ┆┆┃ ┃ ┆┆┃ ━ ┃ ┆┆┃ ┳┛ ┗┳ ┃ ┆┆┃ ┃ ┆┆┃ ┻ ┃ ┆┆┗━┓ ┏━┛ ┆┆ ┃ ┃ ┆ ┆ ┃ ┗━━━┓ ┆┆ ┃ AC代马 ┣┓┆┆ ┃ ┏┛┆┆ ┗┓┓ ┏━┳┓ ┏┛ ┆┆ ┃┫┫ ┃┫┫ ┆┆ ┗┻┛ ┗┻┛ ┆
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define me(a,b) memset(a,b,sizeof(a))
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
using namespace std;
const int maxm=2e6+5;
const int maxn=1e5+4;
int s[1000][55];
const int N=128;
struct node
{char ss[55];int num;
}a[maxn];
struct AC
{int fail[maxn];int ch[maxn][130];int val[maxn];int vis[maxn];int cnt,root;int newnode(){for(int i=0;i<N;i++)ch[cnt][i]=0;val[cnt]=fail[cnt++]=0;return cnt-1;}void init(){cnt=0;root=newnode();}void insert(char *s,int x){int len=strlen(s);int u=0;for(int i=0;i<len;i++){int v=s[i];if(!ch[u][v])ch[u][v]=newnode();u=ch[u][v];}val[u]=x;}void getfail(){queue<int >q;for(int i=0;i<N;i++)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<N;i++){if(ch[u][i]){fail[ch[u][i]]=ch[fail[u]][i];q.push(ch[u][i]);}elsech[u][i]=ch[fail[u]][i];}}}void queuy(char *s){int len=strlen(s);int u=0;for(int i=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z'){int v=s[i];u=ch[u][v];for(int j=u;j;j=fail[j])//判断条件只需要看是否到根结点，不用记录走过的路径{if(val[j])a[val[j]].num++;}}else//如果我们找到了一个非大写字母，下一个你肯定要从头找起u=0;}}
}AC;
char str[maxm];
int main()
{int n;while(scanf("%d",&n)!=EOF){AC.init();for(int i=1;i<=n;i++){scanf("%s",a[i].ss);a[i].num=0;AC.insert(a[i].ss,i);}AC.getfail();scanf("%s",str);AC.queuy(str);for(int i=1;i<=n;i++)if(a[i].num)printf("%s: %d\n",a[i].ss,a[i].num);}return 0;
}
这篇关于HDU 3065病毒侵袭持续中 AC自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
