版子题,练手。只不过这里要统计数量,所以还是有一点变化
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 50004;
using namespace std;
const int max_n = 5e4 + 100;
const int max_m = 2e6 + 100;
struct AC_Automation {
int teir[max_n][30];
int fail[max_n];
int is[max_n];
int res[1100];
int cnt = 0;
int tot = 0;
void init() {
memset(teir, 0, sizeof(teir));
memset(fail, 0, sizeof(fail));
memset(is, 0, sizeof(is));
memset(res, 0, sizeof(res));
cnt = tot = 0;
}
void insert(char* p) {
int cur = 0;int n = strlen(p);
for (int i = 0;i < n;++i) {
if (teir[cur][p[i] - 'A' + 1] == 0)
teir[cur][p[i] - 'A' + 1] = ++cnt;
cur = teir[cur][p[i] - 'A' + 1];
}is[cur] = ++tot;
}void build() {
queue<int> que;
for (int i = 0;i <= 26;++i)
if (teir[0][i] != 0)
que.push(teir[0][i]);
while (!que.empty()) {
int u = que.front();que.pop();
for (int i = 0;i <= 26;++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 cur = 0;int n = strlen(s);
for (int i = 0;i < n;++i) {
if (s[i] > 'Z' || s[i] < 'A')cur = 0;
else cur = teir[cur][s[i] - 'A' + 1];
for (int j = cur;j;j = fail[j])
++res[is[j]];
}
}
}ac;
int N;
char p[1100][55];
char s[max_m];
int main() {
while (scanf("%d", &N)!=EOF) {
ac.init();
for (int i = 1;i <= N;++i) {
scanf("%s", &p[i]);
ac.insert(p[i]);
}scanf("%s", &s);
ac.build();
ac.quiry(s);
for (int i = 1;i <= N;++i)
if (ac.res[i] != 0)
printf("%s: %d\n", p[i], ac.res[i]);
}
}