首页 > 代码库 > HDU 2222 Keywords Search （AC自动机）
HDU 2222 Keywords Search （AC自动机）
题意：给你一些模式串，再给你一串匹配串，问你在匹配串中出现了多少种模式串，模式串可以相同
AC自动机：trie树上进行KMP。首先模式串建立trie树，再求得失配指针（类似next数组），其作用就是在这一位不匹配时转移到失配指针上。失配指针是转移到某个等于此位置最长后缀的位置，求法是bfs
#include<set>#include<map>#include<queue>#include<stack>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstring>#include<stdlib.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0#define mul(a,b) (a<<b)#define dir(a,b) (a>>b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=1000010;const int NumSize=26;struct node{ int next[NumSize],coun; int fail;//fail指针 void init() { memset(next,0,sizeof(next)); coun=fail=0; }} ACFA[Max];int tot;void Init(){ tot=0; ACFA[tot].init(); return;}char str[Max];void Insert(int len)//添加{ int now=0,mpos; for(int i=0; i<len; ++i) { mpos=str[i]-‘a‘; if(!ACFA[now].next[mpos]) { ACFA[now].next[mpos]=++tot; ACFA[tot].init(); } now=ACFA[now].next[mpos]; } ACFA[now].coun++; return;}int que[Max];//bfs构造fail指针void GetFail()//构造fail指针{ int top=0,bot=0; int now,fail; for(int i=0;i<NumSize;++i)//入队 if(ACFA[0].next[i]) que[top++]=ACFA[0].next[i]; while(top!=bot) { now=que[bot++]; for(int i=0;i<NumSize;++i) { if(ACFA[now].next[i]) { que[top++]=ACFA[now].next[i]; fail=ACFA[now].fail; while(fail&&!ACFA[fail].next[i])//寻找失配指针位置 fail=ACFA[fail].fail; if(ACFA[fail].next[i])//找到 fail=ACFA[fail].next[i]; ACFA[ACFA[now].next[i]].fail=fail; } else//建立trie图 ACFA[now].next[i]=ACFA[ACFA[now].fail].next[i]; } } return;}int Search(int len){ int ans=0; int mpos,nowp,now=0; for(int i=0;i<len;++i) { mpos=str[i]-‘a‘; while(now>0&&!ACFA[now].next[mpos])//失配后 now=ACFA[now].fail; if(ACFA[now].next[mpos])//找到 { now=ACFA[now].next[mpos]; nowp=now; while(nowp&&ACFA[nowp].coun!=-1)//-1找过 { ans+=ACFA[nowp].coun; ACFA[nowp].coun=-1; nowp=ACFA[nowp].fail; } } } return ans;}int main(){ int t,n; scanf("%d",&t); while(t--) { Init(); scanf("%d",&n); for(int i=0; i<n; ++i) { scanf("%s",str); Insert(strlen(str)); } GetFail(); scanf("%s",str); printf("%d\n",Search(strlen(str))); } return 0;}
HDU 2222 Keywords Search （AC自动机）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。