题目大意：
给定n个字符串连成了一篇文章，问每个字符串在这篇文章中出现的次数，可重复覆盖
这里ac自动机和后缀数组都可以做
当然后缀数组很容易就解决，但是相对时间消耗高
这里就只讲ac自动机了
将每个字符串放入ac自动机中，这里需要记录到达每个ac自动机上的节点出现这个状态有多少次
而我们添加字符串进入的时候，应该是把经过的每个节点的val都++，说明这个字符串多出现了一次这个值
然后因为自己用字符串在ac自动机上走肯定是到达离root最近的点，也就是说有很多的点会不断通过fail指针指向他，而这些点都是包含了这个字符串的
那也就是说我们需要考虑 val[fail[i]] += val[i]
这里一定是需要从最底层的点不断fail上来，我们需要找到一个合适的更新val点的顺序
可以考虑在我们构建后缀自动机的时候我们采用的是利用队列bfs的过程，那也就是说进入的点是符合最大长度从小到大的性质的
而fail指向的总是比它长度更小的点，所以根据进入队列的点的逆顺序来更新val即可
也就是每次点进队列都 que[cnt++] = u;
最后
for(int i=sz-1 ; i>0 ; i--)
val[fail[que[i]]]+=val[que[i]];
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define clr(x) memset(x , 0 , sizeof(x))
#define set(x) memset(x , -1 , sizeof(x))
typedef long long LL ; const int CHAR_SIZE = ;
const int MAX_SIZE = ;
const int M = ; struct AC_Machine{
int ch[MAX_SIZE][CHAR_SIZE] , val[MAX_SIZE] , fail[MAX_SIZE] , que[MAX_SIZE];
int sz;
bool vis[MAX_SIZE];
void init(){
sz = ;
clr(ch[]) , clr(val) , clr(vis);
} int insert(string s){
int n = s.length();
int u= ;
for(int i= ; i<n ; i++){
int c = s[i]-'a';
if(!ch[u][c]){
clr(ch[sz]) , val[sz]=;
ch[u][c] = sz++;
}
u = ch[u][c];
val[u]++;
}
return u;
} void get_fail(){
queue<int> Q;
fail[] = ;
int cnt = ;
for(int c= ; c<CHAR_SIZE ; c++){
int u = ch[][c];
if(u){Q.push(u);fail[u]=,que[cnt++]=u;}
}
while(!Q.empty()){
int r = Q.front();
Q.pop();
for(int c= ; c<CHAR_SIZE ; c++){
int u = ch[r][c];
if(!u){ch[r][c] = ch[fail[r]][c]; continue;}
fail[u] = ch[fail[r]][c];
Q.push(u);
que[cnt++]=u;
}
}
}
void updateVal(){
for(int i=sz- ; i> ; i--)
val[fail[que[i]]]+=val[que[i]];
}
}ac;
int n , pos[];
string s[]; int main()
{
// freopen("a.in" , "r" , stdin);
// freopen("out.txt" , "w" , stdout);
scanf("%d" , &n);
ac.init();
for(int i= ; i<n ; i++){
cin>>s[i];
pos[i] = ac.insert(s[i]);
}
ac.get_fail();
ac.updateVal();
for(int i= ; i<n ; i++)
printf("%d\n" , ac.val[pos[i]]);
return ;
}