AC自动机模板

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <iostream>
  4  
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <algorithm>
  8 #include <cmath>
  9  
 10 #include <queue>
 11 #include <vector>
 12 #include <map>
 13 #include <set>
 14 #include <stack>
 15 #include <list>
 16  
 17 typedef unsigned int uint;
 18 typedef long long int ll;
 19 typedef unsigned long long int ull;
 20 typedef double db;
 21  
 22 using namespace std;
 23  
 24 inline int getint()
 25 {
 26     int res=0;
 27     char c=getchar();
 28     bool mi=false;
 29     while(c<‘0‘ || c>‘9‘) mi=(c==‘-‘),c=getchar();
 30     while(‘0‘<=c && c<=‘9‘) res=res*10+c-‘0‘,c=getchar();
 31     return mi ? -res : res;
 32 }
 33 inline ll getll()
 34 {
 35     ll res=0;
 36     char c=getchar();
 37     bool mi=false;
 38     while(c<‘0‘ || c>‘9‘) mi=(c==‘-‘),c=getchar();
 39     while(‘0‘<=c && c<=‘9‘) res=res*10+c-‘0‘,c=getchar();
 40     return mi ? -res : res;
 41 }
 42  
 43 db eps=1e-20;
 44 inline bool feq(db a,db b)
 45 { return fabs(a-b)<eps; }
 46 
 47 template<typename Type>
 48 inline Type avg(const Type a,const Type b)
 49 { return a+((b-a)/2); }
 50 
 51 //==============================================================================
 52 //==============================================================================
 53 //==============================================================================
 54 //==============================================================================
 55 
 56 int n,m;
 57 char S[105000];
 58 char inp[105000];
 59 
 60 struct node
 61 {
 62     node*s[26];
 63     node*trans[26];
 64     node*f;
 65     node*p; //parent.
 66     bool leaf; //is terminal ?
 67     char v; //witch character this node represent ?
 68     node()
 69     { memset(s,0,sizeof(s)); f=p=NULL; leaf=false; }
 70 }pool[105000];
 71 node*pt=pool;
 72 
 73 node*qc[105000];
 74 node*qf[105000];
 75 int qh,qt;
 76 
 77 struct Trie
 78 {
 79     node*root;
 80     Trie(){ root=pt++; root->v=‘*‘-‘a‘; }
 81     
 82     void Insert(char*f,int len)
 83     {
 84         node*x=root;
 85         for(int i=0;i<len;i++)
 86         {
 87             int v=f[i]-‘a‘;
 88             if(x->s[v]==NULL)
 89             {
 90                 x->s[v]=pt++;
 91                 x->s[v]->p=x;
 92                 x->s[v]->v=v;
 93             }
 94             x=x->s[v];
 95         }
 96         x->leaf=true;
 97     }
 98     
 99     void Construct()
100     {
101         node*x=root;
102         qh=qt=0;
103         for(int i=0;i<26;i++)
104         if(x->s[i]!=NULL)
105         {
106             x->s[i]->f=root;
107             for(int j=0;j<26;j++)
108             if(x->s[i]->s[j]!=NULL)
109                 qc[qt]=x->s[i]->s[j],qf[qt]=root,qt++;
110         }
111         
112         while(qh!=qt)
113         {
114             node*cur=qc[qh];
115             node*fp=qf[qh];
116             
117             while(fp!=root && fp->s[cur->v]==NULL) fp=fp->f;
118             if(fp->s[cur->v]!=NULL) fp=fp->s[cur->v];
119             cur->f=fp;
120             
121             for(int i=0;i<26;i++)
122                 if(cur->s[i]!=NULL)
123                     qc[qt]=cur->s[i],qf[qt]=fp,qt++;
124             
125             qh++;
126         }
127     }
128     
129     node*GetTrans(node*x,int v)
130     {
131         if(x->s[v]!=NULL)
132             return x->trans[v]=x->s[v];
133         
134         if(x->trans[v]==NULL)
135         {
136             if(x==root) return root;
137             
138             return x->trans[v]=GetTrans(x->f,v);
139         }
140         
141         return x->trans[v];
142     }
143 
144     
145     
146     void output() { output(root); }
147     void output(node*x)
148     {
149         printf("%c %02d %p %p %p \n",x->v+‘a‘,x->v,x,x->f,x->p);
150         for(int i=0;i<26;i++)
151         if(x->s[i]!=NULL) output(x->s[i]);
152     }
153 }T;
154 
155 node*_step[105000];
156 node**step=_step+1;
157 int _prev[105000];
158 int*prev=_prev+1;
159 
160 int main()
161 {
162     freopen("censor.in","r",stdin);
163     freopen("censor.out","w",stdout);
164     
165     scanf("%s",S);
166     n=strlen(S);
167     m=getint();
168     for(int i=0;i<m;i++)
169     {
170         scanf("%s",inp);
171         T.Insert(inp,strlen(inp));
172     }
173     
174     T.Construct();
175     
176     step[-1]=T.root;
177     prev[-1]=-1;
178     for(int i=0;i<n;i++)
179     prev[i]=i-1;
180     
181     for(int i=0;i<n;i++)
182     {
183         step[i]=T.GetTrans(step[i-1],S[i]-‘a‘);
184 
185         if(step[i]->leaf) //we found a word.
186         {
187             node*p=step[i];
188             int cur=i;
189             while(p!=T.root && cur!=-1)
190             {
191                 S[cur]=0;
192                 p=p->p;
193                 cur=prev[cur];
194             }
195             
196             step[i]=step[cur];
197             prev[i+1]=cur;
198         }
199     }
200     
201     for(int i=0;i<n;i++)
202     if(S[i]!=0)
203     printf("%c",S[i]);
204     printf("\n");
205     
206     
207     return 0;
208 }