继续填坑，出完了互测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，那么我们就可以直接跑过去啦。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAX=256,Tr=5010*10,LO=5010;struct tree{    int w,f;    int t[MAX];}t[Tr];int n,m,mm,num=0;char c[LO];int s[LO];queue 
          
            q;inline void in(int nu){    int p=0,l;    for (register int i=0;i
          
         
        
       
      

 

模板题(HDU 2222)：

#include
      
       #include
       
        #include
        
         #include
         
          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 
          
            q;inline void in(){    int p=0,l;    for (register int i=0;i
          
         
        
       
      

 

最后推荐几发博客：

http://blog.csdn.net/niushuai666/article/details/7002823

http://www.cnblogs.com/kuangbin/p/3164106.html

以及一个题库：