每次匹配都不停跳fail显然太慢了，于是在每个节点和fail指向的点连一条边，构成一棵树，在这棵树上差分一下就好了。
AC自动机 就这个算法而言其实没用想象中那么难。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
int fail, next[26], num;
}AC[200010];
int n, u, cnt;
queue <int> q;
int p[200010], vis[200010];
char a[2000010];
int f[200010];
struct Edge{
int next, to;
}e[200010];
int head[200010], num;
inline void Add(int from, int to){
e[++num].to = to; e[num].next = head[from]; head[from] = num;
}
void insert(int x){
int len = strlen(a + 1), w;
u = 0;
for(int i = 1; i <= len; ++i){
w = a[i] - 'a';
if(!AC[u].next[w])
AC[u].next[w] = ++cnt;
u = AC[u].next[w];
}
f[x] = u;
}
void BuildFail(){
u = 0;
for(int i = 0; i < 26; ++i)
if(AC[u].next[i])
q.push(AC[u].next[i]);
while(q.size()){
u = q.front(); q.pop();
for(int i = 0; i < 26; ++i)
if(AC[u].next[i]){
q.push(AC[u].next[i]);
AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i];
}
else
AC[u].next[i] = AC[AC[u].fail].next[i];
}
}
void Match(){
int len = strlen(a + 1);
u = 0;
for(int i = 1; i <= len; ++i){
u = AC[u].next[a[i] - 'a'];
++vis[u];
}
}
void dfs(int x){
for(int i = head[x]; i; i = e[i].next){
dfs(e[i].to); vis[x] += vis[e[i].to];
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i) f[i] = i;
for(int i = 1; i <= n; ++i){
scanf("%s", a + 1);
insert(i);
}
scanf("%s", a + 1);
BuildFail();
Match();
for(int i = 1; i <= cnt; ++i)
Add(AC[i].fail, i);
dfs(0);
for(int i = 1; i <= n; ++i)
printf("%d
", vis[f[i]]);
return 0;
}