计蒜客♂计蒜客♂计蒜客♂计蒜客

[模板]AC自动机

2019-04-01 19:36:26


#include <bits/stdc++.h>
using namespace std;
const int maxlen = 1000010;
namespace Trie{
    struct node{
        int fail,cnt,nxt['z'-'a'+2];
        node(){memset(nxt,0,sizeof nxt);}
    }trie[maxlen];
    int tid = 0;
    void insert(int id,char *str){
        int len = strlen(str);
        for(int i=0;i<len;i++){
            int now = str[i] - 'a';
            if(trie[id].nxt[now] == 0){
                //new node
                trie[id].nxt[now] = ++tid;
            }
            id = trie[id].nxt[now];
        }
        trie[id].cnt++;
    }
}
namespace ACAuto{
    void getFail(int id){
        queue<int> q;
        for(char c='a';c<='z';c++){
            int now = Trie::trie[id].nxt[c-'a'];
            if(now){
                q.push(now);
                Trie::trie[id].fail = id;
            }
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(char c='a';c<='z';c++){
                int v = Trie::trie[u].nxt[c-'a'];
                if(!v) {
                    Trie::trie[u].nxt[c-'a'] = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
                    continue;
                }
                Trie::trie[v].fail = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
                q.push(v);
            }
        }
    }

    long long query(int id,char *str){
        long long ans = 0;
        int len = strlen(str);
        for(int i=0;i<len;i++){
            int now = Trie::trie[id].nxt[str[i]-'a'];
            while(now && Trie::trie[now].cnt != -1){
                ans += Trie::trie[now].cnt;
                Trie::trie[now].cnt = -1;
                now = Trie::trie[now].fail;
            }
            id = Trie::trie[id].nxt[str[i]-'a'];
        }
        return ans;
    }
}
int n;
char tmp[maxlen];
int main(){
    //freopen("testdata.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",tmp);
        Trie::insert(0,tmp);
    }
    ACAuto::getFail(0);
    scanf("%s",tmp);
    printf("%lld\n",ACAuto::query(0,tmp));
    return 0;
}