AC自动机

本文主要是介绍AC自动机，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

学习博客

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define ull unsigned long long
#define N 1001000
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct ACzdj{
    int tr[N][26],cnt;
    int end[N];int fail[N];
    
    inline void insert(char *s){
        int p=0;
        for(int i=0;s[i];i++){
            int k=s[i]-'a';
            if(!tr[p][k]) tr[p][k]=++cnt;
            p=tr[p][k];
        }
        end[p]++;
    }
    
    inline void build(){
        queue<int> q;
        memset(fail,0,sizeof(fail));
        for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
        while(q.size()){
            int top=q.front();q.pop();
            for(int i=0;i<26;i++){
                if(tr[top][i]){
                    fail[tr[top][i]]=tr[fail[top]][i];
                    q.push(tr[top][i]);
                }
                else tr[top][i]=tr[fail[top]][i];
            }
        }
    }
    
    inline void clear(){
        memset(tr,0,sizeof(tr));
        memset(end,0,sizeof(end));
        memset(fail,0,sizeof(fail));
        cnt=0;
    }
    
    inline int query(char *t){
        int p=0,res=0;
        for(int i=0;t[i];i++){
            p=tr[p][t[i]-'a'];
            for(int j=p;j&&~end[j];j=fail[j]) res+=end[j],end[j]=-1;
        }
        return res;
    }
};
ACzdj ac;

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        char s[N];
        scanf("%s",s);
        ac.insert(s);
    }
    ac.build();
    char t[N];
    scanf("%s",t);
    int ans=ac.query(t);
    printf("%d",ans);
    return 0;
}

这篇关于AC自动机的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！