悬关一个。

题目大意是求有多少个模板串在模式串中出现了。多测。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n, T;
struct node {
    node *s[26];
    node *fail;
    bool appear;
    node() {
        for (int i = 0; i < 26; i ++ ) 
            s[i] = nullptr;
        fail = nullptr; appear = false;
    }
    ~node() {};
    
    void insert(string str) {
        auto now = this;
        for (auto i : str) {
            int v = i - 'a';
            if (now -> s[v] == nullptr)
                now -> s[v] = new node();
            now = now -> s[v];
        }
        now -> appear = true;
    }
    
    void get_fail() {
        queue<node*> q; q.push(this);
        while (q.size()) {
            auto t = q.front(); q.pop();
            for (int i = 0; i < 26; i ++ ) {
                if (t -> s[i] == nullptr) continue;
                q.push(t -> s[i]);
                auto fa = t -> fail;
                if (t == this) { // 是根节点出边的，fail 指针都指向根节点
                    t -> s[i] -> fail = this;
                    continue;
                }
                while (fa) {
                    if (fa -> s[i]) {
                        t -> s[i] -> fail = fa -> s[i];
                        break;
                    }
                    fa = fa -> fail;
                }
                if (fa == nullptr) t -> s[i] -> fail = this;
            }
        }
    }
    
    int AC(string text) {
        auto now = this; int ans = 0;
        for (auto i : text) {
            int v = i - 'a';
            while (now != nullptr and now -> s[v] == nullptr) now = now -> fail;
            if (now == nullptr) { now = this; continue; }
            now = now -> s[v];
            auto tmp = now;
            while (tmp != this) {
                if (tmp -> appear) {
                    ans ++ ;
                    tmp -> appear = false;
                }
                else break;
                tmp = tmp -> fail;
            }
        }
        return ans;
    }
    void clear() {
        queue<node*> q; q.push(this);
        vector<node*> states;
        while (q.size()) {
            auto t = q.front(); q.pop();
            states.push_back(t);
            for (int i = 0; i < 26; i ++ ) {
                if (t -> s[i] == nullptr) continue;
                q.push(t -> s[i]);
            }
        }
        for (auto t : states) {
            if (t == this) continue;
            if (t == nullptr) continue;
            t = nullptr;
        }
    }
};

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> T; node root;
    while (T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) {
            string str; cin >> str;
            root.insert(str);
        }
        root.get_fail();
        string text; cin >> text;
        cout << root.AC(text) << endl;
        root.clear();
    }
    return 0;
}