3172: [Tjoi2013]单词

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 3246 Solved: 1565
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

Source

在构建trie树时，统计每个节点出现的次数。
AC自动机实现：从前向后倒推，用一个单词的后缀的次数来更新前缀的次数。

/*fail树.（摘自yjy）
一开始没想出用AC自动机怎么做.
原来是fail树处理.
因为fail指针有一个很好的性质
就是某个字串的后缀等于fail指向位置的前缀.
那么显然的p的深度 > p->fail .
我们bfs的时候有一个已经处理好的深度关系.
那么我们倒序相加把贡献转移给文章中给定的前缀串就好了.
那么某个字符串答案的贡献就来源于两部分.
case 1:与该串前缀相同的字串个数.
case 2:与该串前缀不同的字串个数.
对于case 1,我们可以在建trie的时候直接算出来.
    case 2 我们统一把贡献转移给前缀串.
*/
#include<cstdio>
#include<cstring>
#define Sz 26
using namespace std;
const int N=1e6+5,Z=26;
int n,cnt=1,tr[N][Z],tag[N],fail[N],q[N];
int ans[N],f[N];
char s[N];
void insert(int id){
    scanf("%s",s);
    int now=1,l=strlen(s);
    for(int z,i=0;i<l;i++){
        z=s[i]-'a';
        if(!tr[now][z]) tr[now][z]=++cnt;
        now=tr[now][z];
        ans[now]++;
    }
    tag[now]++;f[id]=now;
}
void acmach(){
    for(int i=0;i<Sz;i++) tr[0][i]=1;
    int h=0,t=1,now=1,p;q[t]=1;fail[1]=0;
    while(h!=t){
        now=q[++h];
        for(int i=0;i<Sz;i++){
            if(!tr[now][i]) continue;
            p=fail[now];
            while(!tr[p][i]) p=fail[p];
            p=tr[p][i];
            fail[tr[now][i]]=p;
            q[++t]=tr[now][i];
        }
    }
    for(int i=t;i;i--) ans[fail[q[i]]]+=ans[q[i]];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) insert(i); 
    acmach();
    for(int i=1;i<=n;i++) printf("%d
",ans[f[i]]);
    return 0;
}