题意：链接
方法：AC自己主动机与fail树性质
解析：复习AC自己主动机的第一道题？(真正的第一题明明是又一次写了遍hdu2222！
)
这题说实话第一眼看上去就是个sb题，仅仅要建出来自己主动机。然后搜fail树即可了。只是看完140142的博客貌似这样会T？只是他也过了是什么鬼？反正想想后没想到什么好的方法就去看了看题解。写题解的大牛们的思路能够概括成一句话，也就是fail树的性质：
你要查找某个串的出现次数则为该串的根节点在fail树上出现的次数之和。
恩知道了这个性质后(能够yy下)，这道题能够再来个优化，也就是在build的时候能够将这个整个树的bfs序求出来，又由于fail节点都是后面的连到前面的，所以无后效性，也就是说，我们能够从这个栈的栈顶抽元素，并将他的end值加到他的fail节点上。这样也许会快非常多？
输出部分就是我们之前说的了。找到每一个串的根节点。询问他的end值即可。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 210
#define M 1000100
using namespace std;
int n,L,root,size;
char s[N][M];
int next[M][27],fail[M],end[M],q[M];
int newnode()
{
for(int i=1;i<=26;i++)next[size][i]=-1;
end[size++]=0;
return size-1;
}
void init()
{
size=0;
root=newnode();
}
void ins()
{
int l=strlen(s[L]);
int now=root;
for(int i=0;i<l;i++)
{
int tmp=s[L][i]-'a'+1;
if(next[now][tmp]==-1)next[now][tmp]=newnode();
now=next[now][tmp];
end[now]++;
}
}
void build()
{
int LL=0,RR=-1;
for(int i=1;i<=26;i++)
{
if(next[root][i]==-1)next[root][i]=root;
else
{
fail[next[root][i]]=root;
q[++RR]=next[root][i];
}
}
while(LL<=RR)
{
int u=q[LL++];
for(int i=1;i<=26;i++)
{
if(next[u][i]==-1)next[u][i]=next[fail[u]][i];
else
{
fail[next[u][i]]=next[fail[u]][i];
q[++RR]=next[u][i];
}
}
}
for(int i=RR;i>=0;i--)
{
end[fail[q[i]]]+=end[q[i]];
}
}
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
L++;
ins();
}
build();
L=1;
for(int i=1;i<=n;i++)
{
int k=root;
int l=strlen(s[i]);
for(int j=0;j<l;j++)k=next[k][s[i][j]-'a'+1];
printf("%d\n",end[k]);
}
}