AC自動機

#include <iostream>
#include <cstring>
#define mem(v,x) memset(v,x,sizeof v)

using namespace std;
const int N = 400025, K = 26;

struct AhoCorasick {
    int tot, ch[N][K], ans[N], fail[N]; // root = 0
    int q[N], head, tail; // queue 儲存BFS順序以計算答案
    void init() {
        tot = head = tail = 0;
        mem(ch, 0), mem(ans, 0), mem(fail, 0);
    }
    int ins(const string &s) {
        int i = 0;
        for(char c: s) {
            if(!ch[i][c-'a']) ch[i][c-'a'] = ++tot;
            i = ch[i][c-'a'];
        }
        return i;
    }
    void get_fail() {
        for(int c = 0; c < K; c++) if(ch[0][c]) q[tail++] = ch[0][c];
        while(head != tail) {
            int i = q[head++];
            for(int c = 0; c < K; c++) if(ch[i][c]) {
                int j = fail[i];
                while(j && !ch[j][c]) j = fail[j];
                if(ch[j][c]) j = ch[j][c];
                fail[ch[i][c]] = j;
                q[tail++] = ch[i][c];
            }
        }
    }
    void run(const string &s) {
        int i = 0;
        for(char c: s) {
            while(i && !ch[i][c-'a']) i = fail[i];
            if(ch[i][c-'a']) i = ch[i][c-'a'];
            ++ans[i];
        }
        for(int i = tot-1; i >= 0; i--) {
            int x = q[i];
            ans[fail[x]] += ans[x];
        }
    }
} AC;
int endnode[N];
void solve() {
    int n;
    string T, P;
    cin >> T >> n;
    AC.init();
    for(int i = 0; i < n; i++) cin >> P, endnode[i] = AC.ins(P);
    AC.get_fail();
    AC.run(T);
    for(int i = 0; i < n; i++) cout << AC.ans[endnode[i]] << '\n';
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}