传送门
题面：
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 5091 Solved: 2491
[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
题目分析：
对于这个题目，首先我们可以用一种最无脑的做法。我们可以先将所有的单词压入AC自动机内，然后对于每次的单词，我们在trie树上暴力的跳转匹配。但是这个题的数据量比较庞大，直接跳转匹配求次数时间上会接受不了。因此我们需要另辟途径。
现在我们需要引入Fail树的概念。
简单来说，Fail树就是将AC自动机上每一个结点的失配指针反置而形成的一颗树。因为AC自动机中fail指针指向与该节点表示串后缀相等的且长度最大的串(或前缀)的节点，因此Fail树也存在着一个很强的性质：1、它的每个点都是一个字符串的前缀，而且每个字符串的每个前缀在这棵树上都对应着一个点。2、每个点父节点的字符串都是这个点字符串的后缀，并且树上没有更长的它的后缀。
因此，我们可以发现，要求出某一个串（结点）的信息，实质上就是求出他的子树所包含的信息。
对于这个题，我们可以在建立Trie树的过程中，将其经过的每一个结点都size+1，最后建立出Fail树之后，用以此dfs去遍历整颗树，并且向上更新父亲结点的size。之后我们所需要的答案即是每一个单词的结尾的字符所在的结点的size。
代码：
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int num[maxn];
char s[maxn];
struct edge{
int from,to,next;
}q[maxn];
int head[maxn],cnt=0;
void add_edge(int from,int to){//手动建立Fail树
cnt++;
q[cnt].from=from;
q[cnt].to=to;
q[cnt].next=head[from];
head[from]=cnt;
}
struct Trie{//AC自动机模板
int next[maxn][26],fail[maxn],End[maxn],root,id;
int newnode(){
for(int i=0;i<26;i++){
next[id][i]=-1;
}
End[id]=0;
return id++;
}
void init(){
id=0;
root=newnode();
}
void Insert(char *str,int id){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
if(next[now][str[i]-'a']==-1){
next[now][str[i]-'a']=newnode();
}
now=next[now][str[i]-'a'];
End[now]++;//不断在经过的每一个结点+1
}
num[id]=now;
}
void build(){
queue<int>que;
for(int i=0;i<26;i++){
if(next[root][i]==-1){
next[root][i]=root;
}
else{
fail[next[root][i]]=root;
que.push(next[root][i]);
}
}
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=0;i<26;i++){
if(next[now][i]==-1){
next[now][i]=next[fail[now]][i];
}
else{
fail[next[now][i]]=next[fail[now]][i];
que.push(next[now][i]);
}
}
}
}
}ac;
void dfs(int x){//用dfs向上扩展父亲结点的的大小
for(int i=head[x];i!=-1;i=q[i].next){
int to=q[i].to;
dfs(to);
ac.End[x]+=ac.End[to];
}
}
int main()
{
int n;
scanf("%d",&n);
ac.init();
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i<=n;i++){
scanf("%s",s);
ac.Insert(s,i);
}
ac.build();
for(int i=1;i<ac.id;i++){
add_edge(ac.fail[i],i);
}
dfs(0);
for(int i=1;i<=n;i++){
printf("%d
",ac.End[num[i]]);
}
return 0;
}