病毒侵袭

版子题，练手

#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int max_n = 1e5 + 100;
set<int> ans;
queue<int> que;
struct AC_Automation {
    int teir[max_n][130];
    int cnt = 1;int tot = 0;
    int is[max_n];
    int fail[max_n];
    void insert(char* p) {
        int cur = 0;int n = strlen(p);
        for (int i = 0;i < n;++i) {
            if (teir[cur][p[i]] == 0)
                teir[cur][p[i]] = cnt++;
            cur = teir[cur][p[i]];
        }is[cur] = ++tot;
    }void build() {
        for (int i = 1;i < 130;++i)
            if (teir[0][i] != 0)
                que.push(teir[0][i]);
        while (!que.empty()) {
            int  u = que.front();que.pop();
            for (int i = 1;i < 130;++i) {
                if (teir[u][i] != 0) {
                    fail[teir[u][i]] = teir[fail[u]][i];
                    que.push(teir[u][i]);
                }
                else teir[u][i] = teir[fail[u]][i];
            }
        }
    }void quiry(char* s) {
        int n = strlen(s);
        int cur = 0;
        for (int i = 0;i < n;++i) {
            cur = teir[cur][s[i]];
            for (int j = cur; j && is[j] != 0; j = fail[j])
                ans.insert(is[j]);
        }
    }
}ac;
char p[210];
char s[max_n];
int N, M;
int main() {
    ios::sync_with_stdio(0);
    cin >> N;
    for (int i = 1;i <= N;++i) {
        cin >> p;
        ac.insert(p);
    }ac.build();
    cin >> M;int total = 0;
    for (int i = 1;i <= M;++i) {
        cin >> s;
        ac.quiry(s);
        if (!ans.empty()) {
            ++total;
            cout << "web " << i << ":";
            for (int it : ans)
                cout << " " << it;
            cout << endl;
        }ans.clear();
    }cout << "total: " << total << endl;
}