Bzoj3172 [Tjoi2013]单词

3172: [Tjoi2013]单词

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 2859 Solved: 1367

Description

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

题解注：论文即是所有的单词集

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

借这题重构了ac自动机的代码(学习自hzw大神)

因为要用来匹配的也是之前的单词，所以不需要最后拼好“论文”再匹配。插入时先记下每个单词的结束位置，建完树后统计有多少fail指针指到该结束位置，即是该单词的数量。

刚开始用STL队列做的，之后发现不方便统计fail指针位置，又强行改成了数组队列。

↑AC

再之后想到STL队列，也可以直接从最后的cnt倒序遍历到1，统计fail指针位置，也不会影响结果（根节点设为0，无用的fail指针最后都指向0），只是稍微多循环了几次。

↑这个懒得验证了，好像不一定对？

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 int n;
 8 char s[1000020];
 9 int w[1000020];
10 struct ACa{
11     int next[1000020][26],fail[1000020];
12     int q[1000020];
13     int end[1000020];
14     int root,cnt;
15     int hd,tl;
16     void clear(){cnt=1;    root=1;for(int i=0;i<26;i++)next[0][i]=1;}
17     int insert(int &pos){
18         int now=root;
19         int len=strlen(s);
20         for(int i=0;i<len;i++){
21             if(!next[now][s[i]-'a']){
22                 next[now][s[i]-'a']=++cnt;
23             }
24             now=next[now][s[i]-'a'];
25             end[now]++;
26         }
27         pos=now;
28     }
29     void Build(){
30         hd=0;tl=1;
31         q[0]=root;
32         fail[root]=0;
33         while(hd<tl){
34             int now=q[hd];
35             hd++;
36             for(int i=0;i<26;i++){
37                 int v=next[now][i];
38                 if(!v)continue;
39                 int k=fail[now];
40                 while(!next[k][i])k=fail[k];
41                 fail[v]=next[k][i];
42                 q[tl++]=v;
43             }
44         }
45     }
46     void query(){
47         for(int i=tl-1;i>=0;i--)end[fail[q[i]]]+=end[q[i]];
48     }
49 };
50 ACa ac;
51 int main(){
52     scanf("%d",&n);
53     int i,j;
54     ac.clear();
55     for(i=1;i<=n;i++)scanf("%s",s),ac.insert(w[i]);
56     ac.Build();
57     ac.query();
58     for(i=1;i<=n;i++)printf("%d
",ac.end[w[i]]);
59 }