【BZOJ3172】[Tjoi2013]单词

Description

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

Input

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

Output

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

题解：先用AC自动机求出fail树，然后使每个单词上的每一个节点的权值都+1，在fail树里处理一下子树的权值和。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

const int maxn=1000010;

struct node

{

    int fail,ch[26],sum;

}p[maxn];

int n,m,tot;

int Q[maxn],ans[maxn],pos[maxn];

char w[maxn];

queue<int> q;

int main()

{

    scanf("%d",&n);

    int i,j,k,u,t;

    tot=1;

    for(i=1;i<=n;i++)

    {

        scanf("%s",w);

        u=1;

        k=strlen(w);

        for(j=0;j<k;j++)

        {

            if(!p[u].ch[w[j]-'a'])    p[u].ch[w[j]-'a']=++tot;

            u=p[u].ch[w[j]-'a'];

            p[u].sum++;

        }

        pos[i]=u;

    }

    q.push(1);

    while(!q.empty())

    {

        u=q.front(),q.pop();

        Q[++Q[0]]=u;

        for(i=0;i<26;i++)

        {

            if(!p[u].ch[i])    continue;

            q.push(p[u].ch[i]);

            if(u==1)

            {

                p[p[u].ch[i]].fail=1;

                continue;

            }

            t=p[u].fail;

            while(!p[t].ch[i]&&t)    t=p[t].fail;

            if(t)    p[p[u].ch[i]].fail=p[t].ch[i];

            else    p[p[u].ch[i]].fail=1;

        }

    }

    for(i=tot;i>=2;i--)    p[p[Q[i]].fail].sum+=p[Q[i]].sum;

    for(i=1;i<=n;i++)    printf("%d\n",p[pos[i]].sum);

    return 0;

}

秒客网

【BZOJ3172】[Tjoi2013]单词 AC自动机