90pts TLE on#9求条

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
const int ALPHA = 26;

int ch[N][ALPHA];
int fail[N];
int cnt[N];              // cnt[u] 表示以节点 u 结尾的单词个数（或是否为结尾）
int idx = 0;

// 插入一个模式串 s
void insert(const string& s){
    int u = 0;
    for (char c : s) {
        int v = c - 'a';
        if (!ch[u][v]) ch[u][v] = ++idx;
        u = ch[u][v];
    }
    cnt[u]++;
}

void build(){
    queue<int> q;
    // 根的所有直接子节点入队，fail 指向 0
    for(int i = 0; i < ALPHA; i++){
        if (ch[0][i]) {
            fail[ch[0][i]] = 0;
            q.push(ch[0][i]);
        }
    }
    while(!q.empty()){
        int u = q.front(); 
		q.pop();
        for(int i=0; i<ALPHA; i++){
            if(ch[u][i]){
                int v = ch[u][i];
                fail[v] = ch[fail[u]][i];  //利用父节点的 fail 快速转移
                q.push(v);
            } 
			else{
                ch[u][i] = ch[fail[u]][i]; //把空指针直接指向 fail 的对应子
            }
        }
    }
}

// 在文本串 t 中匹配，返回匹配到的单词总数
int query(const string& t){
    int u = 0, res = 0;
    for(char c : t){
        u = ch[u][c-'a'];
        for(int j = u; j; j = fail[j]){  // 沿 fail 链向上统计所有匹配
            res += cnt[j];
            cnt[j] = 0;
        }
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        string s;
        cin >> s;
        insert(s);
    }
    build();
    string t;
    cin >> t;
    cout << query(t) << '\n';
    return 0;
}