【AC自动机】HDUOJ 2222+3065+2896
在模式匹配过程中,如果模板有很多个,KMP算法就不太合适了,因为每次查找一个模板,都要遍历整个文本串。可不可以只遍历一次文本串呢?可以,方法是把所有模板建成一个大的状态转移图(称为Aho-Corasick自动机,简称AC自动机),而不是每个模板各建一个状态转移图。注意到KMP的状态转移图是线性的字符串加上失配边组成的,不难想到AC自动机是Trie加上失配边组成的。
AC自动机详解:http://blog.csdn.net/niushuai666/article/details/7002823
本人学习就是参考这个博客,对AC自动机有了简单的理解,重点是fail指针的构造转移。下面来看一个模板题,AC自动机入门:
题目链接:http://acm.hdu.edu.cn/showPRoblem.php?pid=2222
#include<stdio.h> #include<algorithm> #include<string.h> #include<iostream> #include<stdlib.h> #include<math.h> #include<queue> #include<map> #include<stack> using namespace std; #define mann 500010 #define INF 0x3f3f3f3f #define Max 1e14+10 typedef long long LL; struct Trie { int next[mann][26],fail[mann],end[mann]; int root,L; int newnode() { for(int i=0;i<26;i++) next[L][i]=-1; end[L++]=0; return L-1; } void init()//初始化 { L=0; root=newnode(); } void insert(char buf[])//建立字典树 { int len=strlen(buf); int now=root; for(int i=0;i<len;i++) { if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } end[now]++;//标记根节点 } void build()//fail指针的构造,匹配失败时要跳到的位置,AC自动机的核心,自己慢慢体会 { queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()) { int now=Q.front(); Q.pop(); for(int i=0;i<26;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int query(char buf[])//遍历查询 { int len=strlen(buf); int now=root; int res=0; for(int i=0;i<len;i++) { now=next[now][buf[i]-'a']; int temp=now; while(temp!=root) { res+=end[temp]; end[temp]=0; temp=fail[temp]; } } return res; } }; char buf[mann*2]; Trie ac; int main() { int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); ac.init(); for(int i=0;i<n;i++) { scanf("%s",buf); ac.insert(buf); } ac.build(); scanf("%s",buf); printf("%d\n",ac.query(buf)); } return 0; }推荐题目1:http://acm.hdu.edu.cn/showproblem.php?pid=3065
按顺序输出文本串中出现每个模式串的个数。和上一题差不多,标记不同。注意字符串中字符都是ASCII码可见字符(不包括回车)。
#include<stdio.h> #include<algorithm> #include<string.h> #include<iostream> #include<stdlib.h> #include<math.h> #include<queue> #include<map> #include<stack> using namespace std; #define mann 500010 #define INF 0x3f3f3f3f #define Max 1e14+10 typedef long long LL; struct Trie { int next[mann][128],fail[mann],end[mann]; int root,L; int newnode() { for(int i=0; i<128; i++) next[L][i]=-1; end[L++]=-1; return L-1; } void init() { L=0; root=newnode(); } void insert(char buf[],int id) { int len=strlen(buf); int now=root; for(int i=0; i<len; i++) { if(next[now][buf[i]]==-1) next[now][buf[i]]=newnode(); now=next[now][buf[i]]; } end[now]=id; } void build() { queue<int>Q; fail[root]=root; for(int i=0; i<128; i++) if(next[root][i]==-1) next[root][i]=root; else { fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()) { int now=Q.front(); Q.pop(); for(int i=0; i<128; i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else { fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int num[mann]; void query(char buf[]) { memset(num,0,sizeof(num)); int len=strlen(buf); int now=root; int res=0; for(int i=0; i<len; i++) { now=next[now][buf[i]]; int temp=now; while(temp!=root) { if(end[temp]!=-1) num[end[temp]]++; //res+=end[temp]; //end[temp]=0; temp=fail[temp]; } } //return res; } }; char buf[mann*4]; char ss[1005][150]; Trie ac; int main() { int n,m; while(~scanf("%d",&n)) { ac.init(); for(int i=0; i<n; i++) { scanf("%s",ss[i]); ac.insert(ss[i],i); } ac.build(); scanf("%s",buf); ac.query(buf); for(int i=0;i<n;i++) { if(ac.num[i]) printf("%s: %d\n",ss[i],ac.num[i]); } } return 0; }推荐题目2:http://acm.hdu.edu.cn/showproblem.php?pid=2896
问你目标串中出现几个模式串,然后把每个出现模式串的ID按顺序输出。用num数组标记统计一下就好,和HDU3065(上一题)的标记一样,输出格式不同而已。