Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
a
aa
aaa
Sample Output
6
3
1
3
1
fail树的DP
AC自动机的性质，fail指针指向的地方保证前缀相同，所以倒着跑DP就好了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 1000000000
#define mod 1000000007
const int N=;
struct acm{
int cnt;
int next[][],sum[],fail[],q[];
char ch[];
acm(){
cnt=;
for (int i=;i<;i++) next[][i]=;
}
void ins(int &pos){
int now=;
scanf("%s",ch);
int n=strlen(ch);
for (int i=;i<n;i++){
if(!next[now][ch[i]-'a'])
next[now][ch[i]-'a']=++cnt;
now=next[now][ch[i]-'a'];
sum[now]++;
}
pos=now;
}
void buildfail(){
int head=,tail=;
q[]=,fail[]=;
while(head!=tail){
int now=q[head];head++;
for(int i=;i<;i++){
int v=next[now][i];
if(!v) continue;
int k=fail[now];
while(!next[k][i]) k=fail[k];
fail[v]=next[k][i];
q[tail++]=v;
}
}
for(int i=tail-;i>=;i--)
sum[fail[q[i]]]+=sum[q[i]];//就是这里啦！！！
}
}acm;
int n,pos[N];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++) acm.ins(pos[i]);
acm.buildfail();
for (int i=;i<=n;i++) printf("%d\n",acm.sum[pos[i]]);
}