版子题,练手
#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;
}