AC自动机---个人总结

比较好的 AC自动机算法详解..

【转】http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

个人总结：【图是盗用的..】

ac自动机是用来求出：给出n个单词，和一篇文章arr[]，问arr中出现了多少个单词..

第一步：根据给出的n个单词构造一棵字典树

第二步：根据字典树完成失配指针

第三步：枚举文章中的每个字符，并根据拥有了失配指针的字典树查找出现的单词个数

以单词：say she shr he her 文章：yasherhs 举例：

第一步：根据给出的n个单词构造一棵字典树

 const int kind = ;

 struct node{

      node *fail;       //失败指针

      node *next[kind]; //Tire每个节点的个子节点（最多个字母）

      int count;        //是否为该单词的最后一个节点

      node(){           //构造函数初始化

          fail=NULL;

          count=;

          memset(next,NULL,sizeof(next));

      }

  }*q[];          //队列，方便用于bfs构造失败指针

  char keyword[];     //输入的单词

  char str[];    //模式串

  int head,tail;        //队列的头尾指针

结构体

  void insert(char *str,node *root){

      node *p=root;

      int i=,index;

      while(str[i]){

          index=str[i]-'a';

          if(p->next[index]==NULL) p->next[index]=new node();

          p=p->next[index];

          i++;

      }

      p->count++;     //在单词的最后一个节点count+1，代表一个单词

  }

构造字典树

AC自动机---个人总结

第二步：根据字典树完成失配指针

<结果是 (she)每一个字符(s,h,e)都会指向自己上一个字符(root,s,h)的失配指针(root,root,root->h)后的和当前字符匹配((如果没有则指向root)root, root->h, root->h->e)的字符>

即结果是保证树中的节点(node)会指向拥有相同字符串(parents->..->node = root->..->node'，parents表示某个祖先节点，node'表示相同字符节点)的枝桠（没有则指向root）

 void build_ac_automation(node *root){

      int i;

      root->fail=NULL;

      q[head++]=root;

      while(head!=tail){

          node *temp=q[tail++];

          node *p=NULL;

          for(i=;i<;i++){

              if(temp->next[i]!=NULL){

                  if(temp==root) temp->next[i]->fail=root;

                  else{

                      p=temp->fail;

                      while(p!=NULL){

                          if(p->next[i]!=NULL){

                              temp->next[i]->fail=p->next[i];

                              break;

                          }

                          p=p->fail;

                      }

                      if(p==NULL) temp->next[i]->fail=root;

                  }

                  q[head++]=temp->next[i];

              }

          }

      }

  }

完成失配指针

AC自动机---个人总结

第三步：枚举文章中的每个字符，并根据拥有了失配指针的字典树查找出现的单词个数 <cnt += node.cnt>

  int query(node *root){

      int i=,cnt=,index,len=strlen(str);

      node *p=root;

      while(str[i]){

          index=str[i]-'a';

          while(p->next[index]==NULL && p!=root) p=p->fail;

          p=p->next[index];

          p=(p==NULL)?root:p;

          node *temp=p;

          while(temp!=root && temp->count!=-){

              cnt+=temp->count;

              temp->count=-;

              temp=temp->fail;

          }

          i++;

      }

      return cnt;

  }

查找

查找方法是如果上一个字符的下一个字符和当前字符匹配，则加上node.cnt，并不断按照失配指针查找出现的单词，不断加上node.cnt

失配，则根据失配指针去找可能匹配的出现的单词，找到则加上node.cnt

秒客网

AC自动机---个人总结

相关文章