3172: [Tjoi2013]单词

时间：2023-12-30 12:30:44

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+,Z=;

int n,cnt=,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=,l=strlen(s);

    for(int z,i=;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=;i<Sz;i++) tr[][i]=;

    int h=,t=,now=,p;q[t]=;fail[]=;

    while(h!=t){

        now=q[++h];

        for(int i=;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=;i<=n;i++) insert(i);

    acmach();

    for(int i=;i<=n;i++) printf("%d\n",ans[f[i]]);

    return ;

}

相关文章