本文主要是介绍BZOJ 3172 [Tjoi2013]单词 AC自动机 模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
a
aa
aaa
Sample Output
6
3
1
3
1
HINT
Source
题目传送门
开心~又在bzoj找到一题水题。。
注意一下题目题意有点点不清晰。。。
其实总的串是N个单词全部连接起来，而且每两个之间有一个空格（也可以用其它字符代替）
还有就是是N个单词全部连起来的长度<=10^6……
题目比较良心的地方是内存开了512M，这样子的话可以直接上trie[][]了。
总之是一道水水的模板题吧。。
#include<bits/stdc++.h>
using namespace std;
const intN=1000205,NUM=205;
int n,cnt,LenAll;
int pp[N];
int Ans[NUM],fail[N],num[N],Q[N];
int trie[N][27];
char All[N],tmp[N];
int find(int x,int t){if (trie[x][t]) return trie[x][t];if (!x) return 0;return find(fail[x],t);
}
void insert(int ii){int len=strlen(tmp),now=0;for (int i=0;i<len;i++){int j=tmp[i]-'a';if (trie[now][j]) now=trie[now][j];else now=trie[now][j]=++cnt;}if (num[now]) pp[ii]=num[now];else num[now]=ii;
}
void AC(){int head=0,tail=1;Q[0]=0;while (head!=tail){int now=Q[head++];for (int i=0;i<27;i++){if (!trie[now][i]) continue;int t=find(fail[now],i);if (!now) t=0;fail[trie[now][i]]=t;Q[tail++]=trie[now][i];}}
}
void solve(){int now=0;for (int i=0;i<LenAll;i++){int j=All[i]-'a';now=find(now,j);for (int j=now;j;j=fail[j])if (num[j]) Ans[num[j]]++;}
}
int main(){scanf("%d",&n);LenAll=cnt=0;for (int i=1;i<=n;i++){scanf("%s",tmp);int len=strlen(tmp);for (int j=0;j<len;j++) All[LenAll++]=tmp[j];All[LenAll++]='{';insert(i);}AC();solve();for (int i=1;i<=n;i++)if (pp[i]) Ans[i]=Ans[pp[i]];for (int i=1;i<=n;i++)printf("%d\n",Ans[i]);return 0;
}
这篇关于BZOJ 3172 [Tjoi2013]单词 AC自动机 模板题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
