AC自动机

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int T[400100][26] = {0};
int last[401000], f[410000], val[410000];
int sz = 0;
void     _Insert(string s){
    int u = 0;
    for (int i = 0; s[i]; i++){
        int c = s[i] - 'a';
        if (!T[u][c]){
            T[u][c] = ++sz;
            val[sz] = 0;            
        }
        u = T[u][c];
    }
    val[u] ++;
}
char s[1000100];
void build(){
    queue<int> q;
    for (int i = 0; i < 26; i++){
        int u = T[0][i];
        if (u){
            f[u] = last[u] = 0;
            q.push(u);
        }
    }
    while (!q.empty()){
        int h = q.front(); q.pop();
        for (int i = 0; i < 26; i++){
            int u = T[h][i], v = f[h];
            if (!u){
                T[h][i] = T[v][i];
                continue;
            }
            q.push(u);
            while (v && !T[v][i]) v = f[v];
            f[u] = T[v][i];
            last[u] = val[f[u]] ? f[u] : last[f[u]];
        }
    }
}

long long sum = 0;
void print(int j){
    if (j){
        sum += val[j];
        val[j] = 0;
        print(last[j]);
    }
}
void aFind(){
    int j = 0;
    for (int i = 0; s[i]; i++){
        int c = s[i] - 'a';
        j = T[j][c];
        if (val[j]) print(j);
        else if (last[j]) print(last[j]);    
    }
}

int main(){
    int t;
    cin>>t;
    while (t--){
        int n; cin>>n;
        memset(T, 0, sizeof(T));sz = 0;
        memset(last, 0 ,sizeof(last));
        memset(f, 0, sizeof (f));
        memset(val, 0, sizeof(val));
        for (int i = 0; i < n; i++){
            string a;
            cin>>a;
            _Insert(a);
        }
        build();
        scanf("%s", s);
        sum = 0;
        aFind();
        printf("%d\n", sum);
    }
}