分析

1. 每次输入一个单词(模板串)就插入到Trie树中
2. 输入字符串s，统计其每个节点p的siz大小
3. 建立fail树，统计一共出现了多少个单词(dfs)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 2e6+10;
char s[M];
int q[N],cnt[N],siz[N];
int h[N], Ne[N],e[N],idx=1;
int n,tr[N][26],ne[N],tot;
void insert(int x)
{
    int p=0;
    for (int i=0;s[i];++i)
    {
        int t=s[i]-'a';
        if (!tr[p][t]) tr[p][t] = ++tot;
        p = tr[p][t];
    }
    cnt[x] = p; // 记录第x个单词的终止节点为p
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
        if(tr[0][i])    
            q[++tt]=tr[0][i];

    while (hh<=tt)
    {
        auto t = q[hh++];
        for (int i = 0; i < 26;++i)
        {
            int j=tr[t][i];
            if(!j) tr[t][i]=tr[ne[t]][i];
            else{
                ne[j]=tr[ne[t]][i];
                q[++tt]=tr[t][i];
            }
        }
    }
}
void add(int a, int b)
{
    e[idx]=b,Ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)     //通过dfs计算父结点大小的值
{
    for(int i=h[u];~i;i=Ne[i])
    {
        int j = e[i];
        dfs(j);
        siz[u] += siz[j];   //父结点加上子节点的大小
    }
}
int main()
{
    memset(h,-1,sizeof h);
    int i, j, u;

    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%s", s);
        insert(i);  //插入每个单词
    }

    build();
    scanf("%s", s);

    int p=0;
    for (i = 0; s[i]; ++i)
    {
        int j=s[i]-'a';
        p = tr[p][j];
        ++siz[p]; // 记录匹配次数
    }

    for (i =1; i <= tot; ++i) add(ne[i], i);    // 建 ne 树(fail树)
    dfs(0); // 统计子树和
    for (i = 1; i <= n; ++i) printf("%d\n", siz[cnt[i]]);

    return 0;
}