题目链接：

题意：给出n个单词。输出每个单词在所有单词中一共出现多少次？

思路:首先将所有单词插入到ac自动机，记录每个节点次数cnt。建立自动机。然后按照建立自动机的顺序，对于节点u以及其fail节点v，cnt[v]+=cnt[u]。最后找到每个单词在自动机的对应节点u，则cnt[u]就是该单词答案。

 

struct node

{

    int next[26],cnt,fail;

    

    void init()

    {

        clr(next,-1); fail=-1; cnt=0;

    }

};

node a[N];

int e;

void insert(char s[])

{

    int i,k,p=0;

    for(i=0;s[i];i++)

    {

        k=s[i]-'a';

        if(a[p].next[k]==-1)

        {

            a[e].init();

            a[p].next[k]=e++;

        }

        p=a[p].next[k];

        a[p].cnt++;

    }

}

int Q[N];

void build()

{

    int L=0,R=0,i,k,p,q;

    FOR0(i,26) if(a[0].next[i]!=-1)

    {

        Q[R++]=a[0].next[i];

        a[a[0].next[i]].fail=0;

    }

    while(L<R)

    {

        k=Q[L++];

        FOR0(i,26) if(a[k].next[i]!=-1)

        {

            p=a[k].next[i];

            q=a[k].fail;

            Q[R++]=p;

            while(q!=-1&&a[q].next[i]==-1) q=a[q].fail;

            if(q!=-1&&a[q].next[i]!=-1) a[p].fail=a[q].next[i];

            else a[p].fail=0;

        }

    }

    for(i=R-1;i>=0;i--)

    {

        a[a[Q[i]].fail].cnt+=a[Q[i]].cnt;

    }

}

char s[201][N];

int n;

int main()

{

    RD(n); a[0].init(); e=1;

    int i,j,k;

    FOR1(i,n) RD(s[i]),insert(s[i]);

    build();

    FOR1(i,n)

    {

        k=0;

        for(j=0;s[i][j];j++) k=a[k].next[s[i][j]-'a'];

        PR(a[k].cnt);

    }

}