AC自动机模板

题解

前置知识：

• C++
• 数据结构

题目链接

P3808 【模板】AC自动机（简单版）
P3808 【模板】AC自动机（加强版）

解题思路

第一题：在文本串中，寻找有多少模式串出现过。
第二题：在文本串中，找到出现次数最多的模式串，并且输出。如有多个结果则输出多个。
两题的本质都是AC自动机。
先构建Trie树，然后依据KMP的思想，构造fail树。然后进行查询。
代码的主要区别在query和insert。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#define N 500010
using namespace std;
queue<int>q;
struct AC
{
    int c[N][26],val[N],fail[N],cnt;
    void ins(char *s)  //建立trie树 下标存储字母 内容存取跳转
    {
        int len = strlen(s);
        int now =0;
        for(int i=0; i<len; i++)
        {
            int v = s[i]-'a';
            if(!c[now][v])
                c[now][v]=++cnt;
            now = c[now][v];
        }
        val[now]++;
    }
    void build()//构建fail树
    {
        for(int i=0; i<26; i++)  //初始化
            if(c[0][i])
                fail[c[0][i]]=0,q.push(c[0][i]);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=0; i<26; i++)
            {
                if(c[u][i])
                    fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);//跳转
                else
                    c[u][i]=c[fail[u]][i];
            }
        }

    }
    int query(char *s)
    {
        int len = strlen(s);
        int now=0,ans=0;
        for(int i=0; i<len; i++)
        {
            now = c[now][s[i]-'a'];
            for(int t=now; t&&~val[t]; t=fail[t])
                ans+=val[t],val[t]=-1;
        }
        return ans;
    }
} ac;
int n;
char p[1000005];
char ch[155][75];
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%s",p),ac.ins(p);
    ac.build();
    scanf("%s",p);
    int ans = ac.query(p);
    printf("%d\n",ans);
    return 0;
}

```     
      
```c++
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cstring>
#define N 1000005
using namespace std;
queue<int>q;
int ans[155];
struct AC
{
    int c[N][26],val[N],fail[N],cnt;
    //建立trie树 下标存储字母 内容存取跳转 v代表模式串的次序
    void ins(char *s,int v)  
    {
        int len = strlen(s);
        int now =0;
        for(int i=0; i<len; i++)
        {
            int v = s[i]-'a';
            if(!c[now][v])
                c[now][v]=++cnt;
            now = c[now][v];
        }
        val[now]=v;
    }
    void build()//构建fail树
    {
        for(int i=0; i<26; i++)  //初始化
            if(c[0][i])
                fail[c[0][i]]=0,q.push(c[0][i]);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=0; i<26; i++)
            {
                if(c[u][i])
                    fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
                    //跳转
                else
                    c[u][i]=c[fail[u]][i];
            }
        }

    }
    void query(char *s)
    {
        int len = strlen(s);
        int now=0;
        memset(ans,0,sizeof(ans));
        for(int i=0; i<len; i++)
        {
            now = c[now][s[i]-'a'];
            for(int t=now; t; t=fail[t])
                ans[val[t]]+=1;
        }

    }
} ac;
int n;
char p[1000005];
char ch[155][75];
int main()
{
   while(~scanf("%d",&n))
   {
       if(n==0) return 0;
       memset(ac.c,0,sizeof(ac.c));
         memset(ac.val,0,sizeof(ac.val));
           memset(ac.fail,0,sizeof(ac.fail));
            ac.cnt=0;
       memset(p,0,sizeof(p));
       memset(ch,0,sizeof(ch));
       memset(ans,0,sizeof(ans));
      q=queue<int>();
        for(int i=1; i<=n; i++)
        scanf("%s",ch[i]),ac.ins(ch[i],i);
    ac.build();
    scanf("%s",p);
    ac.query(p);
    int tmp = 0;
    for(int i=1;i<=n;i++)
    {

        if(tmp<ans[i]) tmp = ans[i];
    }
    cout<<tmp<<endl;
    for(int i=1;i<=n;i++)
    {
        if(tmp==ans[i])
        {
            printf("%s\n",ch[i]);
        }
    }
   }
    return 0;
}