6
3
1
题解：
题目描述：
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
输入格式：
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N≤200，单词长度不超过106。
输出格式：
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
样例：
样例输入：
3
a
aa
aaa
样例输出：
一看是多模式串，首先应该想到是AC自动机。
如果还不会AC自动机，可以转到这篇博客，个人感觉还是写的挺清楚的：AC自动机讲解+[HDU2222]:Keywords Search（AC自动机）。
那么我们考虑怎么去处理。
首先，将所有的文字段压入AC自动机，然后搞Fail指针，基本操作，不再赘述。
end数组的含义为：第i个串在第end[i]号点结束，0表示没有串在当前节点结束。
然后在构建Fail指针的时候，将每个点的BFS序压入队列，每个点的答案只有可能由它上面的点转移而来，所以按此顺序统计不会出错。
最后输出每个串的结尾点统计的答案即可。
代码时刻：
#include<bits/stdc++.h>
using namespace std;
int n;
int cnt=1,nxt[1000001],trie[1000001][30],end[1000001],que[1000001];
int flag[1000001],ans[1000001],sum=1;
char s[2000001];
void insert(char *str,int id)//构建Trie树
{
int len=strlen(str);
int p=1;
for(int i=0;i<len;i++)
{
int ch=str[i]-‘a‘;
if(!trie[p][ch])trie[p][ch]=++cnt;
ans[p=trie[p][ch]]++;//每个点被经过的次数统计
}
end[id]=p;//第i个串在第end[i]号点结束
}
void build()
{
for(int i=0;i<26;i++)trie[0][i]=1;
que[1]=1;
int head=1,tail=1;
while(head<=tail)
{
flag[++sum]=que[head];//BFS序
for(int i=0;i<26;i++)
{
if(!trie[que[head]][i])trie[que[head]][i]=trie[nxt[que[head]]][i];
else
{
que[++tail]=trie[que[head]][i];
nxt[trie[que[head]][i]]=trie[nxt[que[head]]][i];
}
}
head++;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
insert(s,i);
}
build();
for(int i=sum;i>0;i--)ans[nxt[flag[i]]]+=ans[flag[i]];//统计答案
for(int i=1;i<=n;i++)cout<<ans[end[i]]<<endl;//输出每个点结束位置的答案
return 0;
}
rp++
[BZOJ3172]:[Tjoi2013]单词（AC自动机）
原文：https://www.cnblogs.com/wzc521/p/11081471.html