AC自动机洛谷P5357 模板

题目链接：https://www.luogu.org/problem/P5357

题意：给定n(2e5)个模式串和一个文本串，求每个模式串在文本串中出现的次数,模式串总厂不超过2e5,文本串总厂不超过2e6

分析：做过前面两个题后想求出现次数是再简单不过了，但是我们之前暴力跳fail的方法最坏时间复杂度可以到达O(模式串长度*文本串长度)，

因为对于每一次跳fail我们都只使深度减1，那样深度(深度最深是模式串长度)是多少，每一次跳的时间复杂度就是多少。那么还要乘上文本串长度，就几乎是 O(模式串长度 · 文本串长度)的了。

我们可以用拓扑排序优化时间复杂度为O(模式串长度+文本串长度)

想将复杂度改为加法，很显然就是每个点都只经历一次，每次到了这个点后，我们会支教这个点的结果，不继续跳fail，全部加完后再一次性的全部上传来更新其他店的ans。这可以通过拓扑排序来实现。

这个博客讲的很清楚https://www.luogu.org/blog/juruohyfhaha/ac-zi-dong-ji

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
const int inf=0x3f3f3f3f;
typedef long long ll;
#define meminf(a) memset(a,0x3f,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a));
struct node{
    int fail;//失配指针fail
    int vis[26];//子节点的位置，也就是字典树的那26个字母
    int end;//如果是尾节点就记录 
    int ans;//用来记录出现次数 
}AC[200100];
char s[200100];//用来输入模式串
char ss[maxn]; //用来输入文本串 
int cnt=0;//Trie的指针 
int in[maxn];//记录入度
int m[200100],Ans[200100];
void insert(char *s,int pos){
    int len=strlen(s);
    int now=0;//字典树的当前指针
    for(int i=0;i<len;i++){
        //Trie树没有这个子节点 
        if(AC[now].vis[s[i]-'a']==0) AC[now].vis[s[i]-'a']=++cnt;
        //多组输入，需要清除 一个个清除，之前++cnt说明需要用到这个节点了 
        now=AC[now].vis[s[i]-'a'];
    }
    if(AC[now].end==0) AC[now].end=pos;//标记该结点是一个单词的结尾 ,并标记这是第几个单词 
    m[pos]=AC[now].end;//记录当前的单词的位置，可能是它本身，也可能是它重复单词里第一个出现的 
}

void get_fail(){
    queue<int> que;
    for(int i=0;i<26;i++){//把第二层的fail指针都设为0 
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;
            que.push(AC[0].vis[i]);
            in[0]++;
        }            
    }
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=0;i<26;i++){
            if(AC[u].vis[i]!=0){
                //如果当前结点的子节点存在，就将子节点的fail指针指向当前结点fail指针指向的结点的对应子节点处 
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                in[AC[AC[u].fail].vis[i]]++;//被fail指针指向的结点的入度加1 
                que.push(AC[u].vis[i]);
            }
            else AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //否则直接将这个不存在的子节点指向当前结点fail指针指向结点的对应子节点处 
        }
    }
}

void AC_query(char* s){
    int len=strlen(s);
    int now=0;
    for(int i=0;i<len;i++){
        now=AC[now].vis[s[i]-'a'];
        AC[now].ans++;
    }
}

void topo(){
    queue<int> que;
    for(int i=1;i<=cnt;i++)
        if(in[i]==0) que.push(i);
    while(!que.empty()){
        int u=que.front();que.pop();
        if(AC[u].end!=0) Ans[AC[u].end]=AC[u].ans;
        int v=AC[u].fail;
        if(v!=0) in[v]--,AC[v].ans+=AC[u].ans;
        if(in[v]==0) que.push(v);
    }
}

int main(){
    int n;
    scanf("%d",&n);
    cnt=0;
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        insert(s,i);
    }
    AC[0].fail=0;//结束标志     
    get_fail(); //求出失配指针 
    scanf("%s",ss);
    AC_query(ss);
    topo(); 
    for(int i=1;i<=n;i++){
        printf("%d
",Ans[m[i]]);
    }
    return 0;
}

AC自动机 洛谷P5357 模板

AC自动机洛谷P5357 模板