AC自动机原理：

摘自，ORZ大牛

一：构建AC自动机

  同样我也用网上的经典例子，现有say she shr he her 这样5个模式串，主串为yasherhs，我要做的就是哪些模式串在主串中出现过？

1: 构建trie树

    如果看过我前面的文章，构建trie树还是很容易的。

2：失败指针

    构建失败指针是AC自动机的核心所在，玩转了它也就玩转了AC自动机，失败指针非常类似于KMP中的next数组，也就是说，

 当我的主串在trie树中进行匹配的时候，如果当前节点不能再继续进行匹配，那么我们就会走到当前节点的failNode节点继续进行

匹配，构建failnode节点也是很流程化的。

①：root节点的子节点的failnode都是指向root。

②：当走到在“she”中的”h“节点时，我们给它的failnode设置什么呢？此时就要走该节点（h)的父节点(s)的失败指针，一直回溯直

     到找到某个节点的孩子节点也是当初节点同样的字符(h)，没有找到的话，其失败指针就指向root。

     比如：h节点的父节点为s，s的failnode节点为root，走到root后继续寻找子节点为h的节点，恰好我们找到了，（假如还是没

             有找到，则继续走该节点的failnode，嘿嘿，是不是很像一种回溯查找），此时就将 ”she"中的“h”节点的fainode"指向

            "her"中的“h”节点，好，原理其实就是这样。（看看你的想法是不是跟图一样）

针对图中红线的”h，e“这两个节点，我们想起了什么呢？对”her“中的”e“来说，e到root距离的n个字符恰好与”she“中的e向上的n

个字符相等，我也非常类似于kmp中next函数，当字符失配时，next数组中记录着下一次匹配时模式串的起始位置。

动态模板：

char a[1000001],p[55];struct Trie{    Trie *child[26];    Trie *fail; //失败指针    //int num;    int cnt; //由于同一单词可能出现多次。。。    Trie()    {        //num=0;        cnt=0;        fail=0;        memset(child,0,sizeof(child));    }};Trie *root,*s,*lrelia;void Create(char *str){    s=root;    int i=0;    while(str[i])    {        int id=str[i]-'a';        if(s->child[id]==0)        {            s->child[id]=new Trie;        }            s=s->child[id];        i++;    }    s->cnt++;}void makeFail() //一个节点一个节点找fail指针{    Trie *front ;      queue
     
      q ;      q.push(root) ;      while(!q.empty()){          front = q.front() ;          q.pop() ;          for(int i = 0;i < 26;i++){              if(front->child[i] != NULL){    //父结点有孩子i，则找孩子i的fail指针                  if(front == root)                      front->child[i]->fail = root ;//与根结点相连的结点的fail指针都指向根结点                  else{                      Trie *temp = front ;                      while(temp->fail != NULL){         //父结点fail指针非空                          if(temp->fail->child[i] != NULL){       //父结点fail指针指向的结点有孩子i                              front->child[i]->fail = temp->fail->child[i] ;                              break ;                          }                          temp = temp->fail ;//父结点向上转移                      }                      if(temp->fail == NULL)                          front->child[i]->fail = root ;                  }                  q.push(front->child[i]) ;//找到孩子i的fail指针后将孩子i加入队列              }          }      }  }int search(char *str){    Trie *p = root ;      Trie *temp = NULL ;      int i=0,k,ans = 0 ;      while(str[i]){          k=str[i] - 'a' ;          while(p != root && p->child[k] == NULL){                  p = p->fail ;          }          if(p->child[k] != NULL){
   //p记录当前位置最长的后缀匹配，下次从该支继续匹配              p = p->child[k] ;              temp = p ;         //用temp继续找当前位置较短的后缀匹配              while(temp != root && temp->cnt!=0){                  ans +=temp->cnt;                  temp->cnt = 0 ;                  temp = temp->fail ;              }          }          i++;      }      return ans;  }
     

 

静态模板：

struct Trie{    int child[26];    int cnt;    int fail;    Trie()    {      cnt=0;      fail=-1;      memset(child,0,sizeof(child));    }    void set()    {        cnt=0;        fail=-1;        memset(child,0,sizeof(child));    }}t[240005];int p;void Create(char *s){    int root=0,i=0,id;    while(s[i])    {        id=s[i]-'a';        if(t[root].child[id]==0)            t[root].child[id]=p++;        root=t[root].child[id];        i++;    }    t[root].cnt++;}void makeFail() //构造Fail指针{    queue
     
       q;    int root=0,front;    q.push(root);    while(!q.empty())    {        front=q.front();        q.pop();        for(int i=0;i<26;++i)        {            if(t[front].child[i]!=0)            {                if(front==root)                    t[t[front].child[i]].fail=root;                else                 {                    int temp=front;                    while(t[temp].fail!=-1)                    {                        if(t[t[temp].fail].child[i]!=0)                        {                            t[t[front].child[i]].fail=t[t[temp].fail].child[i];                            break;                        }                        temp=t[temp].fail;                    }                    if(t[temp].fail==-1) //fail当然有可能等于0咯                        t[t[front].child[i]].fail=0;                }                q.push(t[front].child[i]);            }        }    }}int Search(char *s) //查找字符串{    int p=0,temp=0;    int i=0,k,ans=0;    while(s[i])    {        k=s[i]-'a';        while(p!=0&&t[p].child[k]==0)            p=t[p].fail;        if(t[p].child[k]!=0)        {            p=t[p].child[k];            temp=p;            while(temp!=0&&t[temp].cnt!=0)            {                ans+=t[temp].cnt;                t[temp].cnt=0;                temp=t[temp].fail;            }        }        i++;    }    return ans;}
     

使用完静态模板后，记得重新初始化t结构数组