ZR 集训 Day21 - AC 自动机、回文树

待办： 学习回文树。 AC 自动机与回文树例题若干。 题单： P5357 【模板】AC 自动机 模板，上代码： C++ #include using namespace std; const int N=2e5+5; struct ACAM{ int tr[N][30]; int fail[N],cnt[N],in[N],id[N],ask[N],ans[N]; int midx,didx; void init(){ midx=didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=cnt[p]=in[p]=id[p]=0; } void insert(string s,int qid){ int p=0; for(int i=0;i q; for(int i=0;i q; for(int i=1;i>n; for(int i=1;i>t; acam.insert(t,i); } acam.build(); cin>>s; acam.query(s); acam.topu(); for(int i=1;i `#include using namespace std; const int N=2e5+5; struct ACAM{ int tr[N][30]; int fail[N],cnt[N],in[N],id[N],ask[N],ans[N]; int midx,didx; void init(){ midx=didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=cnt[p]=in[p]=id[p]=0; } void insert(string s,int qid){ int p=0; for(int i=0;is.size();i++){ if(!tr[p][s[i]-'a']){ tr[p][s[i]-'a']=++didx; clear(tr[p][s[i]-'a']); } p=tr[p][s[i]-'a']; } if(!id[p]) id[p]=++midx; ask[qid]=id[p]; } void build(){ queueint> q; for(int i=0;i26;i++) if(tr[0][i]) q.push(tr[0][i]); while(q.size()){ int p=q.front(); q.pop(); for(int i=0;i26;i++){ if(tr[p][i]){ fail[tr[p][i]]=tr[fail[p]][i],in[tr[fail[p]][i]]++; q.push(tr[p][i]); } else tr[p][i]=tr[fail[p]][i]; } } } void query(string s){ int p=0; for(int i=0;is.size();i++){ p=tr[p][s[i]-'a']; cnt[p]++; } } void topu(){ queueint> q; for(int i=1;ididx;i++) if(!in[i]) q.push(i); while(q.size()){ int p=q.front(); q.pop(); ans[id[p]]=cnt[p],cnt[fail[p]]+=cnt[p],in[fail[p]]--; if(!in[fail[p]]) q.push(fail[p]); } } int get(int qid){ return ans[ask[qid]]; } }acam; int main(){ int n; string t,s; acam.init(); cin>>n; for(int i=1;in;i++){ cin>>t; acam.insert(t,i); } acam.build(); cin>>s; acam.query(s); acam.topu(); for(int i=1;in;i++) coutacam.get(i)"\n"; return 0; }` P2444 [POI 2000 R1] 病毒 首先，我们需要知道一个事情，那就是 AC 自动机构成的 Trie 图是一个完备的“确定性有限状态自动机”，用人话讲就是所有字符集内的有限串都是能在自动机里找到的。 题目里说的无限 01 串实际上可以看作是有限 01 串无限循环下去，映射到 Trie 图上就是一个环，所以我们构建 Trie 图后找环即可。 对于病毒串，我们在串尾打上病毒标记，找环时不走到这个状态即可。 代码： C++ #include using namespace std; const int N=3e4+5; struct ACAM{ int tr[N][2]; int fail[N],tag[N],dan[N]; int didx; void init(){ didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=0; } void insert(string s){ int p=0; for(int i=0;i q; for(int i=0;i>n; for(int i=1;i>t; acam.insert(t); } acam.build(); if(acam.find(0)) cout `#include using namespace std; const int N=3e4+5; struct ACAM{ int tr[N][2]; int fail[N],tag[N],dan[N]; int didx; void init(){ didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=0; } void insert(string s){ int p=0; for(int i=0;is.size();i++){ if(!tr[p][s[i]-'0']){ tr[p][s[i]-'0']=++didx; clear(tr[p][s[i]-'0']); } p=tr[p][s[i]-'0']; } dan[p]=1; } void build(){ queueint> q; for(int i=0;i2;i++) if(tr[0][i]) q.push(tr[0][i]); while(q.size()){ int p=q.front(); q.pop(); for(int i=0;i2;i++){ if(tr[p][i]){ fail[tr[p][i]]=tr[fail[p]][i]; q.push(tr[p][i]); if(dan[tr[fail[p]][i]]) dan[tr[p][i]]=1; } else tr[p][i]=tr[fail[p]][i]; } } } bool find(int u){ if(tag[u]==1) return 1; if(tag[u]==-1) return 0; tag[u]=1; for(int i=0;i2;i++) if(!dan[tr[u][i]]) if(find(tr[u][i])) return 1; tag[u]=-1; return 0; } }acam; int main(){ int n; string t; acam.init(); cin>>n; for(int i=1;in;i++){ cin>>t; acam.insert(t); } acam.build(); if(acam.find(0)) cout"TAK"; else cout"NIE"; return 0; }` P3041 [USACO12JAN] Video Game G 先对所有“组合技”串插入到自动机里，考虑一个状态的价值应该是其 fail 祖先链上的节点价值之和，我们在 build 的时候记录这样一个 vis 数组，之后进行 DP，设 dp_{i,j} 表示选了 i 个字符，当前在 Trie 上的节点 j，有转移方程： dp_{i,tr[j][k]}=\max _{k\in \{'A','B','C'\}}(dp_{i,tr[j][k]},dp_{i-1,j}+vis_{tr[j][k]}) 代码： C++ #include using namespace std; const int N=305,M=1e3+5; struct ACAM{ int tr[N][3]; int fail[N],vis[N],dp[M][N]; int didx; void init(){ didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=vis[p]=0; } void insert(string s){ int p=0; for(int i=0;i q; for(int i=0;i>n>>k; for(int i=1;i>t; acam.insert(t); } acam.build(); cout `#include using namespace std; const int N=305,M=1e3+5; struct ACAM{ int tr[N][3]; int fail[N],vis[N],dp[M][N]; int didx; void init(){ didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=vis[p]=0; } void insert(string s){ int p=0; for(int i=0;is.size();i++){ if(!tr[p][s[i]-'A']){ tr[p][s[i]-'A']=++didx; clear(tr[p][s[i]-'A']); } p=tr[p][s[i]-'A']; } vis[p]++; } void build(){ queueint> q; for(int i=0;i3;i++) if(tr[0][i]) q.push(tr[0][i]); while(q.size()){ int p=q.front(); q.pop(); for(int i=0;i3;i++){ if(tr[p][i]){ fail[tr[p][i]]=tr[fail[p]][i]; vis[tr[p][i]]+=vis[tr[fail[p]][i]]; q.push(tr[p][i]); } else tr[p][i]=tr[fail[p]][i]; } } } int getans(int k){ int res=0; memset(dp,-0x3f,sizeof dp); dp[0][0]=0; for(int i=1;ik;i++) for(int j=0;jdidx;j++) for(int l=0;l3;l++){ if(dp[i-1][j]0) continue; dp[i][tr[j][l]]=max(dp[i][tr[j][l]],dp[i-1][j]+vis[tr[j][l]]); } for(int i=0;ididx;i++) res=max(res,dp[k][i]); return res; } }acam; int main(){ int n,k; string t; acam.init(); cin>>n>>k; for(int i=1;in;i++){ cin>>t; acam.insert(t); } acam.build(); coutacam.getans(k); return 0; }` P4052 [JSOI2007] 文本生成器 正难则反，考虑容斥，至少包含一个可读单词的文本数量就等于所有文本数量减去一个可读单词也不包含的文本数量。对于所有文本的数量，显然为 26^m 个，而对于一个可读单词也不包含的文本数量，可以考虑在模式串结尾状态打上标记，并传递至其fail祖先链上，然后对没有标记的状态 DP 即可。 代码： C++ #include using namespace std; const int N=6005; const int M=105; const int mod=1e4+7; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } struct ACAM{ int tr[N][26]; int fail[N],vis[N],dp[M][N]; int didx; void init(){ memset(dp,0,sizeof dp); didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=vis[p]=0; } void insert(string s){ int p=0; for(int i=0;i q; for(int i=0;i>n>>k; for(int i=1;i>t; acam.insert(t); } acam.build(); cout `#include using namespace std; const int N=6005; const int M=105; const int mod=1e4+7; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } struct ACAM{ int tr[N][26]; int fail[N],vis[N],dp[M][N]; int didx; void init(){ memset(dp,0,sizeof dp); didx=0; clear(0); } void clear(int p){ memset(tr[p],0,sizeof tr[p]); fail[p]=vis[p]=0; } void insert(string s){ int p=0; for(int i=0;is.size();i++){ if(!tr[p][s[i]-'A']){ tr[p][s[i]-'A']=++didx; clear(tr[p][s[i]-'A']); } p=tr[p][s[i]-'A']; } vis[p]++; } void build(){ queueint> q; for(int i=0;i26;i++) if(tr[0][i]) q.push(tr[0][i]); while(q.size()){ int p=q.front(); q.pop(); for(int i=0;i26;i++){ if(tr[p][i]){ fail[tr[p][i]]=tr[fail[p]][i]; vis[tr[p][i]]+=vis[tr[fail[p]][i]]; q.push(tr[p][i]); } else tr[p][i]=tr[fail[p]][i]; } } } int getans(int m){ int res=qpow(26,m); dp[0][0]=1; for(int i=1;im;i++) for(int j=0;jdidx;j++) for(int k=0;k26;k++){ if(vis[j]||vis[tr[j][k]]) continue; (dp[i][tr[j][k]]+=dp[i-1][j])%=mod; } for(int i=0;ididx;i++) res=((res-dp[m][i])%mod+mod)%mod; return res; } }acam; int main(){ int n,k; string t; acam.init(); cin>>n>>k; for(int i=1;in;i++){ cin>>t; acam.insert(t); } acam.build(); coutacam.getans(k); return 0; }`