BZOJ 3172 [Tjoi2013]单词 fail tree

Description#

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

Input#

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

Output#

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

Sample Input#

3
a
aa
aaa

Sample Output#

6
3
1

题解#

fail 树照着打个板子

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<queue>
5
using namespace std;
6
char S[1000005];
7
int Index;
8
struct Trie{
9
    Trie *ch[26];
10
    Trie *fail;
11
    int id,num;
12
    Trie(){memset(ch,0,sizeof(ch));fail=NULL;fail=0;num=0;id=++Index;}
13
}*root,*word[220];
14
void insert(char *s,int x){
15
    int len=strlen(s);
16
    Trie *now=root;
17
    for(int i=0;i<len;i++){
18
        if(!now->ch[s[i]-'a'])now->ch[s[i]-'a']=new Trie();
19
        now=now->ch[s[i]-'a'];
20
        now->num++;
21
    }
22
    word[x]=now;
23
}
24
struct edge{
25
    Trie *END;edge *next;
26
}*first[26000500];
27
void add(Trie *a,Trie *b){
28
    edge *k=new edge;
29
    k->END=b;
30
    k->next=first[a->id];
31
    first[a->id]=k;
32
}
33
void get_fail(){
34
    queue<Trie*> Q;
35
    Trie *now=root,*temp;
36
    Q.push(now);
37
    while(!Q.empty()){
38
        temp=Q.front();Q.pop();
39
        for(int i=0;i<26;i++){
40
            if(temp->ch[i]){
41
                if(temp==root){
42
                    temp->ch[i]->fail=root;
43
                    add(root,temp->ch[i]);
44
                }
45
                else{
46
                    now=temp->fail;
47
                    while(now&&now->ch[i]==NULL) now=now->fail;
48
                    if(now==NULL)add(root,temp->ch[i]),temp->ch[i]->fail=root;
49
                    else add(now->ch[i],temp->ch[i]),temp->ch[i]->fail=now->ch[i];
50
                }
51
                Q.push(temp->ch[i]);
52
            }
53
        }
54
    }
55
}
56
void dfs(Trie *rt){
57
    for(edge *now=first[rt->id];now;now=now->next){
58
        dfs(now->END);
59
        rt->num+=now->END->num;
60
    }
61
}
62
int main()
63
{
64
    int n;
65
    root=new Trie();
66
    scanf("%d",&n);
67
    for(int i=1;i<=n;i++){
68
        scanf("%s",S);
69
        insert(S,i);
70
    }
71
    get_fail();
72
    dfs(root);
73
    for(int i=1;i<=n;i++){
74
        printf("%d\n",word[i]->num);
75
    }
76
}