AC自动机存储一个字符串的集合,把他叫做T.用i(s)表示字符串s的代表节点. 用s(i)表示节点i的代表字符串.
构建需要的时间是 $O(nc)$ 的,n为字符个数,c为字符集的大小.
AC自动机的性质.
1.从根到一个节点的路径是T中某些字串的前缀. (trie 基本性质)
2.从一个节点到叶节点的路径是这个集合中某一个(如果T的元素不可重复)字串的后缀.(trie 基本性质)
3.fail指针构成一棵fail树,树上父亲-儿子节点的关系为: 设父节点代表的字串为f,子节点为s,那么:
f是s的后缀,但不一定是s的前缀. (fail树基本性质)
4.如果s(i)是s(j)的后缀,那么在fail树上,i一定是j的祖先. (fail树基本性质)
AC自动机的一个用处就是匹配.从trie的根节点(经过fail树边/trie树边)到点i的路径条数就是能匹配到点i的字符串个数.
AC自动机的另一个用处是有了fail树以后,我们可以处理一些后缀相关的东西.此类题目大多具有自我匹配的特点,即用T中的字符串匹配T中的元素.
AC USACO 2015 Feb. Gold T2 Censor
一道模板题.....
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 }
具体的,我们维护每个字符在自动机上的到达状态,然后匹配完毕后暴力删掉(用后向链表)匹配完毕的字符串,把当前状态变为删除字符串的前面一个字符的状态再接着匹配......
注意由于有指针跳跃操作,AC自动机的f转移就不能均摊O(n)了,于是要预处理trans表示转移到哪个节点(而不是沿着f跑).....
这里用了记忆化搜索呃.......
另一个模板.
AC BZOJ 1030
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 const int MOD=(10007); 57
58 inline void add(int&a,int&b) 59 { a=(a+b)%MOD; } 60
61
62 struct node 63 { 64 char v; 65 node*s[26]; 66 node*trans[26]; 67 node*f; 68 bool danger; 69 int code; 70 node() 71 { 72 memset(s,0,sizeof(s)); 73 memset(trans,0,sizeof(trans)); 74 f=NULL; 75 danger=false; 76 } 77 }pool[6050]; 78 node*nt=pool; 79
80 node*newnode(char v) 81 { nt->v=v; nt->code=int(nt-pool); return nt++; } 82
83 struct trie 84 { 85 node*root; 86 trie(){ root=newnode('*'-'A'); } 87
88 void Insert(char *f,int len) 89 { 90 node*cur=root; 91 for(int i=0;i<len;i++) 92 { 93 int v=f[i]-'A'; 94 if(cur->s[v]==NULL) 95 cur->s[v]=newnode(v); 96 cur=cur->s[v]; 97 } 98 cur->danger=true; 99 } 100
101 void construct() 102 { 103 queue<node*> q; 104 queue<node*> h; 105
106 for(int i=0;i<26;i++) 107 if(root->s[i]) 108 { 109 root->s[i]->f=root; 110
111 for(int j=0;j<26;j++) 112 if(root->s[i]->s[j]) 113 q.push(root->s[i]->s[j]),h.push(root); 114 } 115
116 while(!q.empty()) 117 { 118 node*x=q.front(); q.pop(); 119 node*p=h.front(); h.pop(); 120
121 //deal with current node.
122 while(p!=root && !p->s[x->v]) p=p->f; 123 if(p->s[x->v]) p=p->s[x->v]; 124 x->f=p; 125
126 if(p->danger) x->danger=true; 127
128 //expend sub trees.
129 for(int i=0;i<26;i++) 130 if(x->s[i]) q.push(x->s[i]),h.push(p); 131 } 132 } 133
134 node* GetTrans(node*x,int v) 135 { 136 if(x->trans[v]) return x->trans[v]; 137 else return x->trans[v]=
138 ( x->s[v] ? x->s[v] : ( x==root ? root : GetTrans(x->f,v) ) ); 139 } 140 }; 141
142 int n,m; 143 char inp[200]; 144
145 trie T; 146
147 int d[105][6050]; 148
149 int main() 150 { 151 n=getint(); 152 m=getint(); 153
154 for(int i=0;i<n;i++) 155 { 156 scanf("%s",inp); 157 T.Insert(inp,strlen(inp)); 158 } 159
160 T.construct(); 161
162 d[0][0]=1; 163 for(int h=1;h<=m;h++) 164 { 165 for(node*x=pool;x<nt;x++) 166 { 167 if(x->danger) continue; 168 for(int i=0;i<26;i++) 169 add(d[h][T.GetTrans(x,i)->code],d[h-1][x->code]); 170 } 171 } 172
173 int res=0; 174 for(node*x=pool;x<nt;x++) 175 if(!x->danger) add(res,d[m][x->code]); 176
177 int de=1; 178 for(int i=0;i<m;i++) 179 de=(de*26)%MOD; 180
181 printf("%d\n",((de-res)%MOD+MOD)%MOD); 182
183 return 0; 184 }
注意 if(p->danger) x->danger=true;这一句,用于判断某字符串是否为另一个字符串的后缀.
不加这个的话,会错掉这个数据"2 2 ABA B",正确输出51.
注意这个题的模式串很小,那个求trans的操作实际上是 $O(n^2)$ 的.
AC BZOJ 3942 USACO Feb. Silver T1 Censoring
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 char a[1005000]; 57 char s[1005000]; 58 int f[1005000]; 59 int tran[1005000][26]; 60 int _pre[1005000]; 61 int*pre=_pre+1; 62 int _state[1005000]; 63 int*state=_state+1; 64
65 inline int ch(char c) { return c-'a'; } 66 inline char revh(int k) { return (char)(k+'a'); } 67
68 char res[1005000]; 69
70 int n,m; 71
72 int main() 73 { 74 scanf("%s%s",s,a); 75 n=strlen(a); 76 m=strlen(s); 77
78 int p=-1; 79 f[0]=p; 80 for(int i=1;i<n;i++) 81 { 82 while(p!=-1 && a[p+1]!=a[i]) p=f[p]; 83 if(a[p+1]==a[i]) p++; 84 f[i]=p; 85 } 86
87 for(int i=0;i<n;i++) 88 for(int j=0;j<26;j++) 89 { 90 char c=revh(j); 91
92 /*
93 int p=i; 94 while(p!=-1 && a[p+1]!=c) p=f[p]; 95 if(a[p+1]==c) p++; 96 tran[i][j]=p; 97 */
98
99 if(a[i+1]==c) tran[i][j]=i+1; 100 else tran[i][j]=( f[i]==-1 ? ( a[0]==c ? 0 : -1 ) : tran[f[i]][j] ); 101 } 102
103 for(int i=0;i<m;i++) pre[i]=i-1; 104 state[-1]=-1; 105 int curp=-1; 106 for(int i=0;i<m;i++) 107 { 108 char c=s[i]; 109
110 if(curp!=-1) 111 curp=tran[curp][ch(c)]; 112 else
113 curp=( a[0]==c )-1; 114
115 state[i]=curp; 116
117 if(curp==n-1) 118 { 119 int p=i; 120 for(int j=0;j<n;j++) 121 { 122 s[p]=0; 123 p=pre[p]; 124 } 125 curp=state[p]; 126 pre[i+1]=p; 127 } 128 } 129
130 for(int i=0;i<m;i++) if(s[i]) printf("%c",s[i]); printf("\n"); 131
132 return 0; 133 }
拿了VJ上A掉的一道题去交结果TLE.......然后发现trans数组的递推的复杂度不对........
由于数据规模极高,要改trans.....WA了两发.......
递推求trans数组的时候注意对自动机的起点(编号-1)的处理.......
AC BZOJ 2434 NOI2011 阿狸的打字机
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 //============================================================================== 44 //============================================================================== 45 //============================================================================== 46 //==============================================================================
47
48
49 int s[105000][26]; 50 int pre[105000]; 51 int f[105000]; 52 int val[105000]; 53 int ncnt=2; 54
55 int root=1; 56
57 char a[105000]; 58 int p[105000],pcnt; 59
60 int n,m; 61
62 void BuildTrie() 63 { 64 int x=1; 65 for(int i=0;i<n;i++) 66 if(islower(a[i])) 67 { 68 int v=a[i]-'a'; 69 if(!s[x][v]) 70 { 71 s[x][v]=ncnt; 72 pre[ncnt]=x; 73 val[ncnt]=v; 74 ncnt++; 75 } 76 x=s[x][v]; 77 } 78 else if(a[i]=='P') 79 p[++pcnt]=x; 80 else if(a[i]=='B') 81 x=pre[x]; 82 } 83
84 typedef pair<int,int> pl; 85 queue<pl> q; 86 void BuildAutomaton() 87 { 88 for(int i=0;i<26;i++) 89 if(s[1][i]) 90 { 91 f[s[1][i]]=1; 92 for(int j=0;j<26;j++) 93 if(s[s[1][i]][j]) 94 q.push(pl(s[s[1][i]][j],1)); 95 } 96
97 while(!q.empty()) 98 { 99 int x=q.front().first; 100 int p=q.front().second; 101 q.pop(); 102 int v=val[x]; 103
104 while(p!=1 && !s[p][v]) p=f[p]; 105 if(s[p][v]) p=s[p][v]; 106 f[x]=p; 107
108 for(int i=0;i<26;i++) 109 if(s[x][i]) q.push(pl(s[x][i],p)); 110 } 111
112 } 113
114 struct query_link 115 { 116 int x; 117 int t; 118 int res; 119 query_link*nxt; 120
121 }qpool[105000]; 122 query_link*qds[105000]; 123 bool cmp(const query_link&a,const query_link&b) 124 { return a.t<b.t; } 125
126 struct edge 127 { 128 int in; 129 edge*nxt; 130 }pool[105000]; 131 edge*et=pool; 132 edge*eds[105000]; 133 void addedge(int a,int b) 134 { et->in=b; et->nxt=eds[a]; eds[a]=et++; } 135 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)
136
137 int loc[105000]; //points' location record.
138 int lci[105000]; //location's points record.
139 int tot[105000]; 140 int lcnt=0; 141
142 int SeqBuildDFS(int x) 143 { 144 lci[lcnt++]=x; 145 FOREACH_EDGE(e,x) 146 tot[x]+=SeqBuildDFS(e->in); 147 return tot[x]+=1; 148 } 149
150 int t[105000]; 151 void Change(int p,int v) 152 { p++; for(;p<=lcnt;p+=(p&-p)) t[p]+=v; } 153 int Query(int p) 154 { p++; int res=0; for(;p;p-=(p&-p)) res+=t[p]; return res; } 155
156 void DFS(int x) 157 { 158 if(x!=1) Change(loc[x],1); 159
160 for(query_link*q=qds[x];q;q=q->nxt) 161 q->res=Query(loc[q->x]+tot[q->x]-1)-Query(loc[q->x]-1); 162
163 for(int i=0;i<26;i++) 164 if(s[x][i]) DFS(s[x][i]); 165
166 if(x!=1) Change(loc[x],-1); 167 } 168
169
170 int main() 171 { 172 scanf("%s",&a); 173 n=strlen(a); 174
175 BuildTrie(); 176 BuildAutomaton(); 177
178 for(int i=2;i<ncnt;i++) 179 addedge(f[i],i); 180
181 SeqBuildDFS(1); 182
183 for(int i=0;i<lcnt;i++) 184 loc[lci[i]]=i; 185
186 m=getint(); 187 for(int i=0;i<m;i++) 188 { 189 int x=p[getint()]; 190 int y=p[getint()]; 191 qpool[i].x=x; 192 qpool[i].t=i; 193 qpool[i].nxt=qds[y]; 194 qds[y]=&qpool[i]; 195 } 196
197 DFS(1); 198
199 sort(qpool,qpool+m,cmp); 200 for(int i=0;i<m;i++) printf("%d\n",qpool[i].res); 201
202 return 0; 203 }
DFS写的AC自动机TLE了,不造是自己写搓还是复杂度本来就不对..........
在AC自动机的Fail树上各种乱搞.........
要求一个字符串x的对另外一个字符串y的匹配个数.
考虑暴力,就是枚举y的前缀节点,如果一个前缀节点能跳跃到x的节点就把统计量+1.
建出Fail树以后....就是神奇的乱搞.....真的好神奇.....
我们想快速求出,对于每一个询问(x,y),在fail树上,y有多少个节点在x的子树下边.
我们把Trie树DFS一遍,维护当前路径上的所有点(DFS栈中的点)的存在信息.
具体来说,就是把Fail树的DFS序搞出来,每遍历到Trie树上一个节点就把这个节点在DFS序上的代表位置的值+1,离开就-1.这样区间查询一下就能很快求出某一个子树下有多少当前正在DFS栈中的点.....
头一次写DFS序.....DFS序要注意两点,一是代表区间的长度等于子树大小;
二是子树的根一定最先遍历到,所以在它的代表区间的最左边.
AC BZOJ 3172
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 typedef long double ldb; 22
23 using namespace std; 24
25 inline int getint() 26 { 27 int res=0; 28 char c=getchar(); 29 while(c<'0' || c>'9') c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return 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 //============================================================================== 44 //============================================================================== 45 //============================================================================== 46 //==============================================================================
47
48
49 int s[1005000][26]; 50 int v[1005000]; 51 int c[1005000]; 52 int f[1005000]; 53 int ncnt=1; 54 int Insert(char*a,int len) 55 { 56 int x=0; 57 for(int i=0;i<len;i++) 58 { 59 int k=a[i]-'a'; 60 if(!s[x][k]) s[x][k]=ncnt++; 61 x=s[x][k]; c[x]=k; v[x]++; 62 } 63 return x; 64 } 65
66 int q[1005000],qh,qt; 67 int qr[1005000]; 68 void Build() 69 { 70 for(int i=0;i<26;i++) 71 if(s[0][i]) 72 { 73 f[s[0][i]]=0; 74 for(int j=0;j<26;j++) 75 if(s[s[0][i]][j]) 76 { qr[qt]=0; q[qt]=s[s[0][i]][j]; qt++; } 77 } 78
79 while(qh!=qt) 80 { 81 int x=q[qh]; 82 int p=qr[qh]; qh++; 83
84 while(p && !s[p][c[x]]) p=f[p]; 85 if(s[p][c[x]]) p=s[p][c[x]]; 86 f[x]=p; 87
88 for(int i=0;i<26;i++) 89 if(s[x][i]) { q[qt]=s[x][i]; qr[qt]=p; qt++; } 90 } 91
92 //reversed BFS sequence is topological sorted.
93 for(int i=qt-1;i>=0;i--) v[f[q[i]]]+=v[q[i]]; 94 } 95
96 char st[100000]; 97 void DFS(int x,int dep) 98 { 99 if(x) st[dep]=c[x]+'a'; st[dep+1]=0; 100 printf("%d %s %d %c %d\n",x,st,v[x],c[x]+'a',f[x]); 101 for(int i=0;i<26;i++) if(s[x][i]) DFS(s[x][i],dep+1); 102 } 103
104 int n; 105 char inp[1005000]; 106 int loc[1005000]; 107 int main() 108 { 109 n=getint(); 110 for(int i=0;i<n;i++) 111 { 112 scanf("%s",inp); 113 loc[i]=Insert(inp,strlen(inp)); 114 } 115
116 Build(); 117
118 for(int i=0;i<n;i++) printf("%d\n",v[loc[i]]); 119
120 return 0; 121 }
我的AC自动机代码向来比人家长一倍,抄了一下别人的代码结果狂WA不止....改成原始版本后就A了.....
这个题应该也可以用后缀数据结构做....
注意拓扑序不需要用拓扑排序求出来,BFS序的逆序满足拓扑关系.
...