题意：链接

方法：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]);

    }

}