本文共 1615 字，大约阅读时间需要 5 分钟。

   今天还是看AC自动机，终于把模版代码看懂啦，总结一下：

   AC自动机，应用于模式匹配问题，尤其是长文本多模版问题较于KMP算法和字典树更具有优势。方法是把所有模版建成一个大的状态转移图，而不是每个模版各建一个图。KMP算法的状态转移图是线性的字符串+失配边组成的，而AC自动机是字典树+失配边组成的。字典树在判断一个单词是否属于字典时很有优势，但是字典树在判断一个文本包含多少个字典中的单词时就显得不足了，因为对于文本串的每次字符都必须从字典树的跟节点走一遍字典树(很类似于模式串匹配时用的暴力方法)，此时应该用AC自动机。

    模版代码如下：

#include
   
      #include
    
       #include
     
        using namespace std;  const int maxnode=11000;  const int sigma_size=26;  struct AC_Automata  {      int ch[maxnode][sigma_size];      int val[maxnode];   // 每个字符串的结尾结点都有一个非0的val      int f[maxnode];     // fail函数      int last[maxnode];  // last[i]=j表j节点表示的单词是i节点单词的后缀，且j节点是单词节点      int sz;        //初始化0号根节点的相关信息      void init()      {          sz=1;          memset(ch[0],0,sizeof(ch[0]));          val[0]=0;      }        //insert负责构造ch与val数组      //插入字符串,v必须非0表示一个单词节点      void insert(char *s,int v)      {          int n=strlen(s),u=0;          for(int i=0; i