【bzoj3172】[Tjoi2013]单词

2015.04.15 09:23 Wed | 1次阅读 | 旧日oi | 固定链接 | 源码

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树的思想随便搞一搞就行了。。。
好吧我还是负点责任吧
fail树是个神奇的东西,假设我们把每个fail[v]和v之间连一条边,我们可以发现这是一颗树,每个点的子节点代表的串都是包含这个点代表的串
所以我们统计每个节点出现的次数,从后往前依次累加到fail节点上就可以了

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int pos[205];
int n;
struct ACM{
    char s[1000005];
    int son[1000005][26];
    int sum[1000005];
    int cnt;
    void insert(int &pos)
    {
        scanf("%s",s);
        int l=strlen(s),x=0;
        for(int i=0;i<l;i++)
        {
            if(!son[x][s[i]-'a']) son[x][s[i]-'a']=++cnt;
            x=son[x][s[i]-'a'];
            sum[x]++;
        }
        pos=x;
    }
    int q[1000005],f,t;
    int fail[1000005];
    void build()
    {
        q[t++]=0;
        fail[0]=-1;
        while(f<t)
        {
            int now=q[f++];
            for(int i=0;i<26;i++)
            {
                int v=son[now][i];
                if(!v) continue;
                int k=fail[now];
                while(k!=-1&&!son[k][i]) k=fail[k];
                fail[v]=son[k][i];
                q[t++]=v;
            }
        }
        for(int i=t-1;i;i--)
            sum[fail[q[i]]]+=sum[q[i]];
    }
}acm;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    acm.insert(pos[i]);
    acm.build();
    for(int i=1;i<=n;i++)
    printf("%d\n",acm.sum[pos[i]]);
}```