【AC自动机】bzoj3172: [Tjoi2013]单词

fail图上后缀和需要注意一下

Description

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

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

题目分析

考虑暴力：将每一个单词作为文本串匹配，一旦遇到一个单词节点，就向上跳fail统计整条链上的所有单词的贡献。

注意到对于每一个匹配到的单词节点，有一个向上的后缀和的形式在这里。

那么从另一个方式考虑，对于每一个节点，计算有多少子节点会把它统计进答案里。

这样就可以用很自然的fail后缀和来处理这个问题了。

注意

要注意的是，trie图后缀和的统计顺序不能够简单地根据tot...1的顺序。

因为trie图是有分叉的，节点的标号与深度并无关系。

 #include<bits/stdc++.h>

 const int maxn = ;

 const int maxNode = ;

 struct ACAutomaton

 {

     char s[maxn];

     int vis[maxNode];

     std::queue<int> q;

     int stk[maxNode],cnt;

     int fail[maxNode],f[maxNode][],size[maxNode],tot,n;

     void insert(char *s, int t)

     {

         int u = , lens = strlen(s);

         for (int i=; i<lens; i++)

         {

             int c = s[i]-'a';

             if (!f[u][c]) f[u][c] = ++tot;

             u = f[u][c], size[u]++;

         }

         vis[t] = u;

 //        vis[u]++;

     }

24     void count()　　　　　　//其实这里写的冗长了一点

25     {　　　　　　　　　　　　 //如果用手写的队列就不用再开一个数组了

26         for (int i=tot; i>1; i--)

27             size[fail[stk[i]]] += size[stk[i]];

28     }

     void build()

     {

         for (int i=; i<=; i++) f[][i] = ;

         q.push();

         while (q.size())

         {

             int tt = q.front();

             q.pop();

             stk[++cnt] = tt;

             for (int i=; i<=; i++)

                 if (f[tt][i])

                     fail[f[tt][i]] = f[fail[tt]][i], q.push(f[tt][i]);

                 else f[tt][i] = f[fail[tt]][i];

         }

     }

 }f;

 int n;

 char s[]; 

 int main()

 {

     scanf("%d",&n);

     f.tot = ;

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

         scanf("%s",s), f.insert(s, i);

     f.build(), f.count();

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

     return ;

 }

END

秒客网