BZOJ-3172: [Tjoi2013]单词 (AC自动姬 fail树)

朱雀 2021-03-17 15:40 430阅读 0赞

## 3172: \[Tjoi2013\]单词 ##

Time Limit: 10 Sec  Memory Limit: 512 MB  
Submit: 4057  Solved: 1964  
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 ##

这题把fail指针逆向形成了一个叫fail树的东西  fail树的父亲结点一定是儿子节点的子串！！！

![1008642-20170813174542476-2107158051.png][]

#include "bits/stdc++.h"
     using namespace std;
     typedef long long LL;
     const int MAX=1000006;
     int n;
     struct Aho{
         struct state{
             int next[26];
             int cnt,fail;
             state (){
                 memset(next,0,sizeof(next));
                 cnt=fail=0;
             }
         }sst[MAX];
         
         int q[MAX],low,high,tot,size,end[205],sum[MAX];
         
         void init(){
             int i,j;
             low=1,high=tot=size=0;
             memset(sum,0,sizeof(sum));
         }
         
         void insert(char *s){
             int i,j,ls=strlen(s);
             int now=0;
             for (i=0;i<ls;i++){
                 char c=s[i];
                 if (!sst[now].next[c-'a']) sst[now].next[c-'a']=++size;
                 now=sst[now].next[c-'a'];
                 sum[now]++;
             }
             sst[now].cnt++;
             end[++tot]=now;
         }
         
         void build(){
             int i,j;
             int now=0;
             sst[0].fail=-1;
             q[++high]=0;
             while (low<=high){
                 int u=q[low];
                 low++;
                 for (i=0;i<26;i++){
                     if (sst[u].next[i]){
                         if (u==0) sst[sst[u].next[i]].fail=0;
                         else{
                             int v=sst[u].fail;
                             while (v!=-1){
                                 if (sst[v].next[i]){
      //注意 
                                     sst[sst[u].next[i]].fail=sst[v].next[i];
                                     break;
                                 }
                                 v=sst[v].fail;
                             }
                             if (v==-1)
                                 sst[sst[u].next[i]].fail=0;
                         }
                         q[++high]=sst[u].next[i];
                     }
                 }
             }
             for (;high;high--) sum[sst[q[high]].fail]+=sum[q[high]];//注意 
         }
     }aho;
     int main(){
         freopen ("word.in","r",stdin);
         freopen ("word.out","w",stdout);
         int i,j;char s[MAX];
         aho.init();
         scanf("%d\n",&n);
         for (i=1;i<=n;i++){
             gets(s);
             aho.insert(s);
         }
         aho.build();
         for (i=1;i<=n;i++){
             printf("%d\n",aho.sum[aho.end[i]]);
         }
         return 0;
     }

[1008642-20170813174542476-2107158051.png]: /images/1615995538921.png