C/C++教程

AC自动机简单版

本文主要是介绍AC自动机简单版,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn=1e6+10;
int trie[maxn][26],k,cnt[maxn],fail[maxn];
void insert(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int c=s[i]-'a';
        if(!trie[p][c])trie[p][c]=++k;
        p=trie[p][c];
    }
    cnt[p]++;
}
void getfail(){
    queue<int>q;
    for(int i=0;i<26;i++)
        if(trie[0][i])q.push(trie[0][i]),fail[trie[0][i]]=0;
    while(!q.empty()){
        int t=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(trie[t][i]){
                fail[trie[t][i]]=trie[fail[t]][i];
                q.push(trie[t][i]);
            }
            else{
                trie[t][i]=trie[fail[t]][i];
            }
        }
    }
}
int query(char *s){
    int len=strlen(s),p=0,ans=0;
    for(int i=0;i<len;i++){
        p=trie[p][s[i]-'a'];
        for(int i=p;i&&~cnt[i];i=fail[i]){
            ans+=cnt[i];cnt[i]=-1;
        }
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    char s[maxn];
    while(n--){
        scanf("%s",s);
        insert(s);
    }
    getfail();
    scanf("%s",s);
    printf("%d\n",query(s));
}

  

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