【无聊放个模板系列】BZOJ 3172 (AC自动机)

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 #include<stack>
 9 using namespace std;
10 #define Maxn 210
11 #define Maxm 1000010
12 
13 struct node
14 {
15     int son[30],fail,cnt;
16 }t[Maxm];int tot;
17 
18 char s[Maxm];
19 int l,bj[Maxn];
20 
21 void upd(int x)
22 {
23     memset(t[x].son,0,sizeof(t[x].son));
24     t[x].fail=t[x].cnt=0;
25 }
26 
27 void trie(int st)
28 {
29     int now=0;
30     for(int i=1;i<=l;i++)
31     {
32         int ind=s[i]-'a'+1;
33         if(!t[now].son[ind])
34         {
35             t[now].son[ind]=++tot;upd(tot);
36         }
37         now=t[now].son[ind];
38         t[now].cnt++;
39         if(i==l) bj[st]=now;
40     }
41 }
42 
43 queue<int > q;
44 stack<int > sta;
45 void build()
46 {
47     while(!q.empty()) q.pop();
48     
49     q.push(0);
50     while(!q.empty())
51     {
52         int x=q.front();sta.push(x);
53         q.pop();
54         for(int i=1;i<=26;i++) if(t[x].son[i])
55         {
56             if(x&&t[t[x].fail].son[i]) t[t[x].son[i]].fail=t[t[x].fail].son[i];
57             q.push(t[x].son[i]);
58         }
59         else t[x].son[i]=t[t[x].fail].son[i];
60     }
61     while(!sta.empty())
62     {
63         int x=sta.top();sta.pop();
64         t[t[x].fail].cnt+=t[x].cnt;
65     }
66 }
67 
68 int main()
69 {
70     int n;
71     scanf("%d",&n);
72     tot=0;upd(0);
73     for(int i=1;i<=n;i++)
74     {
75         scanf("%s",s+1);
76         l=strlen(s+1);
77         trie(i);
78     }
79     build();
80     for(int i=1;i<=n;i++) printf("%d
",t[bj[i]].cnt);
81     return 0;
82 }

WA了几次之后终于给面子A了【捂脸= =打模板而已嘛- -

多年前手打队列版本

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 
 5 const int Maxn=(int)1e4;
 6 const int Maxl=200;
 7 
 8 struct node
 9 {
10     int son[27],fail,cnt,ans;
11 }t[160357];
12 
13 int n,m,cnt=0;
14 int q[Maxn*Maxl+10],bj[Maxn];
15 char s[Maxl];
16 
17 void floy()
18 {
19     int i;
20     for(i=1;i<=Maxn;i++) t[i].fail=0,t[i].ans=0;
21 }
22 
23 void read() 
24 {
25      memset(bj,0,sizeof(bj));
26      int i,j,x,ind;
27      scanf("%d",&n);
28      getchar();
29      for(i=1;i<=n;i++)
30      {
31          scanf("%s",s+1);
32          m=strlen(s+1);
33          x=0;
34          for(j=1;j<=m;j++)
35          {
36              ind=s[j]-'a'+1;
37              if(!t[x].son[ind]) t[x].son[ind]=++cnt;
38              x=t[x].son[ind];
39              t[x].cnt++;
40              if(j==m) bj[i]=cnt;
41          }
42      }
43 }
44 
45 void Build_AC()
46 {
47     int i,x,y,j;
48     q[0]=0;
49     q[++q[0]]=0;
50     //for(i=1;i<=26;i++)  if(t[0].son[i]) q[++q[0]]=t[0].son[i]; 
51     for(i=1;i<=q[0];i++)
52     {
53         x=q[i];
54         y=t[x].fail;
55         for(j=1;j<=26;j++)
56             if(t[x].son[j])   
57             {                
58                 //t[t[x].son[j]].fail=t[y].son[j];
59                 t[t[x].son[j]].fail=x?t[y].son[j]:x; 
60                 q[++q[0]]=t[x].son[j];   
61             }
62             else t[x].son[j]=t[y].son[j];
63     }
64     for(i=q[0];i>=1;i--)
65     {
66         t[t[q[i]].fail].cnt+=t[q[i]].cnt;
67     }
68     //for(i=1;i<=cnt;i++) printf("%d %d %d %d
",i,t[i].cnt,t[i].fail,t[i].ffail);
69 }
70 
71 int main()
72 {
73     read();
74     Build_AC();
75     for(int i=1;i<=n;i++) printf("%d
",t[bj[i]].cnt);
76     return 0;
77 }

AC自动机

2016-11-18 10:18:14