AC自动机

#include<cstdio>
#include<cstring>
#include<cstdio>
#include<queue>
#define maxn 1000039
using namespace std;
char s[maxn], key[maxn];
queue<int> q;
int trie[maxn][26], id, cnt[maxn], nex[maxn];
void build(){
    for(int i = 0; i < 26; i++){
        if(trie[0][i])q.push(trie[0][i]);
    }
    while(!q.empty()){
        int point = q.front(); q.pop();
        for(int c = 0; c < 26; c++){
            int i = trie[point][c];
            if(!i)continue;
            int j = nex[point];
            while(j&&!trie[j][c])j = nex[j];
            if(trie[j][c])j = trie[j][c];
            nex[i] = j;
            q.push(i);
        }
    }
}
int AC(){
    int res = 0;
    for(int i = 0, j = 0; s[i]; i++){
        int c = s[i] - 'a';
        while(j&&!trie[j][c])j = nex[j];
        if(trie[j][c])j = trie[j][c];
        int tmp = j;
        while(tmp&&cnt[tmp]!=-1){
            res += cnt[tmp];
            cnt[tmp] = -1;
            tmp = nex[tmp];
        }
    }
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    while(n--){
        scanf("%s", key);
        int point = 0;
        for(int i = 0; key[i]; i++){
             int c = key[i] - 'a';
             if(!trie[point][c])trie[point][c] = ++id;
             point = trie[point][c];
        }
        cnt[point]++;
    }
    build();
    scanf("%s", s);
    printf("%d", AC());
    return 0;
}