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

zcysky · 2017-06-22 10:54:50 · 题解

这是一道AC自动机的裸题。

AC自动机（优化后可称Trie图）是一种（可以理解为被过分简化的）有限状态自动机。

所以可以简单的理解为将KMP放在Trie树上。

注意如果每次跳fail边复杂度过高，一次存储完可以进行优化。

这样的AC自动机就成为了Trie图。

不过这题的std是从香港新闻产业来的，加了一个跳转移边的剪枝优化。

被卡常的同学可以看下std……

#include<bits/stdc++.h>
#define N 500010
using namespace std;
queue<int>q;
struct Aho_Corasick_Automaton{
    int c[N][26],val[N],fail[N],cnt;
    void ins(char *s){
        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(){
        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];
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;
}