题解 P3796 【【模板】AC自动机（加强版）】

wxk01 · 2018-04-07 21:09:10 · 题解

AC自动机是结合了KMP的失配指针和TRIE的树形结构的一种算法。

（所以我们要把KMP和TRIE先搞明白）

• AC自动机

就是能自动AC的机器

AC自动机有三个部分，分别是建树，获取失配指针和查询。

先建一棵TRIE树，再把TRIE树上每个节点的失配指针（重点中的重点）求出，最后查询文本。

首先 我们需要定义一些需要用的数组。

     int num[300010];//结点编号
     int ch[300010][26];//子结点
     int fail[300010];//失配指针
     int ans[300010];//答案

• 建树

  这是一个裸TRIE。直接贴代码。

    void insert(string s,int v){
        int now=0;//当前访问的节点
        for(int i=0;i<s.size();i++){
            int o=s[i]-'a';
            if(!ch[now][o])ch[now][o]=++siz;//新编号
            now=ch[now][o];//继续访问
        }
        num[now]=v;//标记
    }

• 获取失配指针

  AC自动机的fail[a]=b且b!=root，则a和b所代表的字符相同且a的父结点的fail值为b的父节点。

  嗯，文字难免有些令人费解，我们把它转化成代码。

    fail[v]=ch[fail[u][i];

  其中v是u的编号为i的子节点。

  可是，如果v不存在呢？也就是说，如果u没有编号为i的子节点呢？

  那么我们就把u的编号为i的节点直接设为fail[u]的编号为i的子节点。代码：

    ch[u][i]=ch[fail[u]][i];

  另外，与root相连的所有结点的fail值为0。

  代码奉上。
  
      void getfail(){
          int now=0;//当前访问
          queue<int>que;//队列
          for(int i=0;i<26;i++)if(ch[0][i])que.push(ch[0][i]),fail[ch[0][i]]=0;//把与根相连的结点push入
          while(!que.empty()){
              int u=que.front();que.pop();//队列pop
              for(int i=0;i<26;i++){
                  int v=ch[u][i];
                  if(v)fail[v]=ch[fail[u]][i],que.push(v);//情况1：v存在
                  else ch[u][i]=ch[fail[u]][i];//情况2：v不存在
              }
          }
      }

这里还有非常重要的一个细节：若fail[a]=b，则root到a的链一定包含root到b的链。

查询

这是一个与KMP最相似的部分。

假设我们要查询s，现在访问到s[i]，s[i]在TRIE树上的编号为now。我们只需定义j=now，然后j不停的fail，期间ans[num[j]]++,答案就出来了。

这些都是基于我刚刚所讲的一个细节。如果root到a的链存在与s，则root到fail[a]的链也存在于s。

这样子的话，所有困难都迎刃而解。

void query(string s){
        int now=0;//当前访问节点
        for(int i=0;i<s.size();i++){
            now=ch[now][s[i]-'a'];//更新节点
            for(int j=now;j;j=fail[j])ans[val[j]]++;//进行答案累计
        }
    }

• AC Code

  本蒟蒻 8044ms的代码。

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    string mob[300010];
    int num[300010];
    int ch[300010][26];
    int fail[300010];
    int ans[300010];
    int temp;
    int n,siz;
    void insert(string s,int v){
        int now=0;
        for(int i=0;i<s.size();i++){
            int o=s[i]-'a';
            if(!ch[now][o])ch[now][o]=++siz;
            now=ch[now][o];
        }
        num[now]=v;
    }
    void getfail(){
        int now=0;
        queue<int>que;
        for(int i=0;i<26;i++)if(ch[0][i])que.push(ch[0][i]),fail[ch[0][i]]=0;
        while(!que.empty()){
            int u=que.front();que.pop();
            for(int i=0;i<26;i++){
                int v=ch[u][i];
                if(v)fail[v]=ch[fail[u]][i],que.push(v);
                else ch[u][i]=ch[fail[u]][i];
            }
        }
    }
    void query(string s){
        int now=0;
        for(int i=0;i<s.size();i++){
            now=ch[now][s[i]-'a'];
            for(int j=now;j;j=fail[j])ans[num[j]]++;
        }
    }
    int main(){
        while(cin>>n&&n){
            memset(num,0,sizeof(num));
            memset(ans,0,sizeof(ans));
            memset(ch,0,sizeof(ch));
            memset(fail,0,sizeof(fail));
            siz=0;
            for(int i=1;i<=n;i++){
                cin>>mob[i];
                insert(mob[i],i);
            }
            getfail();
            string k;
            cin>>k;
            query(k);
            temp=0;
            for(int i=1;i<=n;i++)if(ans[i]>temp)temp=ans[i];
            cout<<temp<<"\n";
            for(int i=1;i<=n;i++)if(ans[i]==temp)cout<<mob[i]<<"\n";
        }
    }

  本蒟蒻萌新，不足之处欢迎私信。