版子题,练手。只不过这里要统计数量,所以还是有一点变化

#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]);
    }
}