洛谷 P3808 【模板】AC自动机（简单版） 题解

一、题目：

洛谷原题

二、代码：

//AC自动机有很多写法，这种写法是比较稳的。
#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

const int maxn=1e6+6;

int n;

string S[maxn],T;

int sz=1,trie[maxn][30],cnt[maxn*30],fail[maxn*30];

inline void insert(string s){
    int p=0;
    for(register int i=0;i<s.size();++i){
        if(!trie[p][s[i]-'a'+1])trie[p][s[i]-'a'+1]=++sz;
        p=trie[p][s[i]-'a'+1];
    }
    ++cnt[p];
}

inline void bfs(void){
    queue<int>q;
    for(register int i=1;i<=26;++i){
        if(trie[0][i])q.push(trie[0][i]),fail[trie[0][i]]=0;
    }
    while(q.size()){
        int x=q.front();q.pop();
        for(register int i=1;i<=26;++i){
            if(!trie[x][i])trie[x][i]=trie[fail[x]][i];
            else{
                q.push(trie[x][i]);
                fail[trie[x][i]]=trie[fail[x]][i];
            }
        }
    }
}

inline int find(){
    int p=0,ans=0;
    for(register int i=0;i<T.size();++i){
        p=trie[p][T[i]-'a'+1];
        for(register int t=p;t&&~cnt[t];t=fail[t])ans+=cnt[t],cnt[t]=-1;
    }
    return ans;
}

int main(){
    cin>>n;
    for(register int i=1;i<=n;++i){
        cin>>S[i];
        insert(S[i]);
    }
    cin>>T;
    bfs();
    printf("%d
",find());
    return 0;
}