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

【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
",p[pos[i]].sum);
    return 0;
}