模板 Fail树

fail树就是将Trie图的Fail指针反指，从而生成一棵树，这个树的性质是：子节点对应字符串为以当前串为后缀，而子节点为原串的前缀，前缀的后缀就是嵌套在原串中的子串。

模板：BZOJ3172

Description

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

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

建完fail树统计子节点个数即可。

代码：

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 struct trnt{

     int ch[];

     int fl;

     int wgt;

     int hd;

 }tr[];

 struct ent{

     int twd;

     int lst;

 }e[];

 int fnd[];

 char tmp[];

 int cnt;

 int siz;

 int n;

 std::queue<int>Q;

 void ade(int f,int t)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=tr[f].hd;

     tr[f].hd=cnt;

 }

 void add(char *a,int x)

 {

     int root=;

     int len=strlen(a+);

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

     {

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

         if(!tr[root].ch[c])

             tr[root].ch[c]=++siz;

         root=tr[root].ch[c];

         tr[root].wgt++;

     }

     fnd[x]=root;

     return ;

 }

 void Build()

 {

     int root=;

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

         if(tr[root].ch[i])

             Q.push(tr[root].ch[i]);

     while(!Q.empty())

     {

         root=Q.front();

         Q.pop();

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

         {

             if(tr[root].ch[i])

             {

                 tr[tr[root].ch[i]].fl=tr[tr[root].fl].ch[i];

                 Q.push(tr[root].ch[i]);

             }else

                 tr[root].ch[i]=tr[tr[root].fl].ch[i];

         }

     }

     /*--------------------------以上是Trie图-------------------*/

     /*--------------------------以下为fail树-------------------*/

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

         ade(tr[i].fl,i);

     return ;

 }

 void dfs(int x)

 {

     for(int i=tr[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         dfs(to);

         tr[x].wgt+=tr[to].wgt;

     }

 }

 int main()

 {

     scanf("%d",&n);

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

     {

         scanf("%s",tmp+);

         add(tmp,i);

     }

     Build();

     dfs();

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

         printf("%d\n",tr[fnd[i]].wgt);

     return ;

 }

巴特西