C++之路进阶——AC自动机（单词）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 int n,pos[1000005];
 9 struct acm
10    {
11     int sz,point[1000005],q[1000005],sum[1000005],a[1000005][26];
12     char ch[1000005];
13     acm()
14     {sz=1;for (int i=1;i<=26;i++) a[0][i]=1;}
15         
16        void insert(int &pos)
17           {
18           scanf("%s",ch);
19                 int now=1;
20                 for (int i=0;i<strlen(ch);i++)
21                      {
22                           int t=ch[i]-‘a‘+1;
23                        if (a[now][t]) now=a[now][t];
24                             else now=a[now][t]=++sz;
25                             sum[now]++;
26                       }
27                 pos=now;
28            } 
29        
30        void acmach()
31           {
32                 int w=1,t=0;
33                 point[1]=0,q[0]=1; 
34                 while (t<w)
35                    {
36                        int now=q[t++];
37                        for (int i=1;i<=26;i++)
38                      {
39                          if (!a[now][i]) continue;
40                          int k=point[now];
41                          while (!a[k][i])k=point[k];
42                          point[a[now][i]]=a[k][i];
43                          q[w++]=a[now][i];
44                          }    
45                    }
46           for (int i=t-1;i>=0;i--)
47               {
48                   sum[point[q[i]]]+=sum[q[i]];
49                          }           
50           }
51        
52    }acm;
53    
54 int main()
55    {
56         scanf("%d",&n);
57         for (int i=1;i<=n;i++)
58            acm.insert(pos[i]);
59         acm.acmach();
60         for (int i=1;i<=n;i++)
61           printf("%d\n",acm.sum[pos[i]]);
62        }