[BZOJ 3172][Tjoi2013]单词（AC自动机）

Description

---

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

Input

---

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

Output

---

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

Sample Input

---

3 a aa aaa

Sample Output

---

6 3 1

Solution

---

莫名RE一次0 0 我也不知道我到底改了哪儿就A了（仔细想想，我好像把数组开小了些？什么鬼）

其实差不多是裸的AC自动机 insert的时候cnt记录经过该节点的次数 最后逆bfs序把cnt加到fail指针的cnt上

#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<queue> using namespace std; int n,siz=0,root; char s[1000005]; struct node{ int next[26],fail,cnt; }Trie[1000005]; int id[205],tot=0; int q[1000005],head,tail; int newnode() { Trie[++siz].fail=0; Trie[siz].cnt=0; for(int i=0;i<26;i++) Trie[siz].next[i]=0; return siz; } void _insert(char *word) { int i=0,p=root; while(word[i]) { int idx=word[i]-'a'; if(!Trie[p].next[idx]) Trie[p].next[idx]=newnode(); p=Trie[p].next[idx]; Trie[p].cnt++; i++; } id[++tot]=p; } void build() { head=tail=0; q[++tail]=root; while(head<tail) { int p=q[++head]; for(int i=0;i<26;i++) { int t=Trie[p].fail; while(t&&!Trie[t].next[i])t=Trie[t].fail; if(Trie[p].next[i]) { Trie[Trie[p].next[i]].fail=t?Trie[t].next[i]:root; q[++tail]=Trie[p].next[i]; } else Trie[p].next[i]=t?Trie[t].next[i]:root; } } } void work() { for(int i=tail;i;i--) { int t=q[i]; Trie[Trie[t].fail].cnt+=Trie[t].cnt; } } int main() { scanf("%d",&n); root=newnode(); for(int i=1;i<=n;i++) { scanf("%s",s); _insert(s); } build();work(); for(int i=1;i<=tot;i++) { printf("%d\n",Trie[id[i]].cnt); } return 0; }