思路：
ac自动机可以用来求一段文本内多个模式串的出现次数，是kmp在trie上的拓展，fail树可以on时间内求每个子串在所有子串的出现次数
就是反向加边建立fail树递推就可以
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int N=1e6 10;
int tr[N][26],n,idx,id[210],f[N],ne[N];
char s[N];
vector<int>ans;
void insert(int i){
int p=0;
for(int i=0;s[i];i ){
int t=s[i]-'a';
if(!tr[p][t])tr[p][t]= idx;
p=tr[p][t];
f[p] ;
}
id[i]=p;
}
void build(){
queue<int>q;
for(int i=0;i<26;i ){
if(tr[0][i])q.push(tr[0][i]);
}
while(q.size()){
int t=q.front();
q.pop();
ans.push_back(t);
for(int i=0;i<26;i ){
int &p=tr[t][i];
if(!p)p=tr[ne[t]][i];
else{
ne[p]=tr[ne[t]][i];
q.push(p);
}
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i ){
cin>>s;
insert(i);
}
build();
for(int i=ans.size()-1;i>=0;i--){
//cout<<ne[ans[i]]<<" "<<ans[i]<<endl;
f[ne[ans[i]]] =f[ans[i]];
}
for(int i=0;i<n;i ){
cout<<f[id[i]]<<endl;
}
}
