继续填坑，出完了互测Round 5 的题目后，又开始无止境的填坑啦……
学AC自动机之前，建议先学学KMP和Tire，这里只给简介
先说tire，说白了就是一颗每个点都代表一个字母的树，然后再带个根，从根到每个叶子节点的路径表示一个字符串。
例如对于字符串AA,AT,AC,AG,GG，我们可以建出一颗这样的树：
由于是字符，每个点开上26或者256个指针就好，方便操作，实在卡空间再换。
建完这样一颗树就方便我们进行什么前缀查询啥的。
KMP就是给一个字符串A和一个字符串B，问A是否为B的一个子串。
其实也就是在暴力基础上做改进，整个流程是这样的：
对A预处理数组f[i]，表示满足f[1...k]=f[i-k+1,i]的最大一个k。（数组从1开始）
逐位比较，失败时不返回开头而是返回f[i]处。
通常我们暴力的时候会枚举起点，然后一位一位比较。然而对于A为"abc abd"，B为"abc abc abd"（实际是没有空格的，空格为了方便看出数据怎么构造的），程序会非常蠢地不会利用之前的比较数据。使用KMP的时候，假设我们现在以B的第一个字符为起点，到c不等于d处会停止，此时暴力会把A的起点挪到B的第二位继续比较，然而KMP发现f[6](即d所在位置)=2，由于我们是在第6个字符处发现不同，说明前面都一样，即B[1...5]=A[1...5]，自然地B[4...5]=A[4...5]。从预处理的数组我们发现A[1...2]=A[4...5]，那么它会把起点挪到B[4]的位置继续比较。这样速度快得多。
AC自动机就是在Tire上把我们的f数组捣鼓出来，遇到的时候直接转到那边去比较，例如：
(略丑)
比方说要在AGG中找上面这些字符串，发现比较AG完成的时候，G指向另一个G，那么我们就可以直接跑过去啦。
模板题(HDU 2222)：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct tree{ int w,f; int t[26]; }t[1000001]; int tt,n,m,num=0; char s[50],c[1000001]; queue <int> q; inline void in(){ int p=0,l; for (register int i=0;i<m;i++){ l=s[i]-‘a‘; if (!t[p].t[l]) t[p].t[l]=++num; p=t[p].t[l]; } t[p].w++; } inline void mafa(){ register int i;int k,p; q.push(0);t[0].f=0; while(!q.empty()){ k=q.front();q.pop(); for (i=0;i<26;i++) if (t[k].t[i]){ p=t[k].f; while((!t[p].t[i])&&p) p=t[p].f; t[t[k].t[i]].f=(k==p)?0:t[p].t[i]; //printf("%d %d %d %d %d\n",i,k,p,t[t[k].t[i]].f,t[p].t[i]); q.push(t[k].t[i]); } } } inline void que(){ register int i,j; int ans=0,k=strlen(c),p=0,x; for (i=0;i<k;i++){ x=c[i]-‘a‘; while(!t[p].t[x]&&p) p=t[p].f; //printf("%d %d %d\n",i,p,ans); p=t[p].t[x]; if (t[p].w) for (j=p;j;j=t[j].f) ans+=t[j].w,t[j].w=0; } printf("%d\n",ans); } int main(){ register int i,j; scanf("%d",&tt); while(tt--){ for (i=0;i<=num;i++) for (j=0;j<=26;j++) t[i].t[j]=0; for (i=0;i<=num;i++) t[i].w=t[i].f=0; num=0; scanf("%d",&n); for (i=1;i<=n;i++){ scanf("%s",s); m=strlen(s); in(); } mafa(); scanf("%s",c); que(); } }
最后推荐几发博客：
http://blog.csdn.net/niushuai666/article/details/7002823
http://www.cnblogs.com/kuangbin/p/3164106.html
原文：http://www.cnblogs.com/Enceladus/p/5293817.html