天天看点

洛谷 P3808 【模板】AC自动机(简单版)

#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=1000000+100;

int trie[maxn][26],sum[maxn],fail[maxn],tot;
int que[maxn];

inline void insert(char* ch){

    int len=strlen(ch);
    int root=0;
    for(int i=0;i<len;i++){

        int ind=ch[i]-'a';
        if(!trie[root][ind]) trie[root][ind]=++tot;
        root=trie[root][ind];
    }
    sum[root]++;
}

inline void build_fail(){

    int l=0;
    int r=1;
    que[l]=0; // que[l]=root=0
    while(l<r){

        int tmp=que[l++];
        for(int i=0;i<=25;i++){

            int node=trie[tmp][i];
            if(node){

                if(tmp==0){

                    fail[node]=0;
                }
                else{

                    int node_tmp=fail[tmp];
                    while(!trie[node_tmp][i] && node_tmp){

                        node_tmp=fail[node_tmp];
                    }
                    if(trie[node_tmp][i]) fail[node]=trie[node_tmp][i];
                    else fail[node]=0;
                }
                que[r++]=node;
            }
        }
    }
}

inline int search(char* ch){

    int len=strlen(ch);
    int root=0;
    int cnt=0;
    for(int i=0;i<len;i++){

        int ind=ch[i]-'a';
        while(!trie[root][ind] && root) root=fail[root];
        root=trie[root][ind];
        if(root){

            int node_tmp=root;
            while(node_tmp){

                if(sum[node_tmp]>=0){

                    cnt+=sum[node_tmp];
                    sum[node_tmp]=-1;
                }
                else break;
                node_tmp=fail[node_tmp];
            }
        }
    }
    return cnt;
}

char str[maxn],ch[maxn];

int main(){

    int n;
    scanf("%d",&n);
    getchar();
        
    for(int i=1;i<=n;i++){

        scanf("%s",ch);
        insert(ch);
    }
    build_fail();
    scanf("%s",str);
    printf("%d\n",search(str));
}