Ac_automaton的板子打熟以后发现碰到题不会做，而且还是比较纯的板子，只要改几处地方就可以，Ac_automation有许多优秀而fantasy的性质，下面粘几个题，来记录一下做题的心得。
1、Keywords Search
这个题最大的问题是我们很可能漏掉一些解。建Ac_automaton（Trie图），额外维护一个size变量，在单词末尾++。
然后我们拿主串在Ac_automaton上面跑，每次都遍历其fail链（及所有前缀fail），因为fail指向某个串的最长后缀，只要把size累加上，就能把可能漏掉的解全都找回来，遍历完后，size=-1，通过这个操作，我们可以保证，当一个节点被便利后，其所有可能更新答案的fail一定已经被遍历，时间复杂度更加优秀。而且照着代码画一画Trie图，发现只要把主串跑一遍，不需要别的操作，因为在Trie树的最底层，我们把空儿子已经指倒了其fail的儿子，形成一张图，这种“类环”模型可以放心大胆的把主串“扔”到Ac_automaton上“跑”一遍。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<map> #include<set> using namespace std; int T,n; char s[1000100]; struct Ac_automation{ int tot; struct node{ node *son[26]; int size; node *fail; node(){ memset(this,0,sizeof(node)); } }; node *root; void init(){ root=new node(); } void insert(){ int l=strlen(s+1); node *now=root; for(int i=1;i<=l;i++){ if(!now->son[s[i]-'a']) now->son[s[i]-'a']=new node(); now=now->son[s[i]-'a']; }now->size++; } void build(){ queue<node*> q; for(int i=0;i<26;i++){ if(root->son[i]){ q.push(root->son[i]); root->son[i]->fail=root; }else root->son[i]=root; } while(!q.empty()){ node *x=q.front(); q.pop(); for(int i=0;i<26;i++){ if(x->son[i]){ x->son[i]->fail=x->fail->son[i]; q.push(x->son[i]); }else x->son[i]=x->fail->son[i]; } } } int query(){ node *now=root; int l=strlen(s+1),ans=0; for(int i=1;i<=l;i++){ now=now->son[s[i]-'a']; for(node *j=now;j!=root&&j->size!=-1;j=j->fail){ ans+=j->size; j->size=-1; } }return ans; } }Ac; int main(){ scanf("%d",&T); while(T--){ Ac.init(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s+1); Ac.insert(); } Ac.build(); scanf("%s",s+1); printf("%d ",Ac.query()); }return 0; }
2、玄武密码
建立Ac_automaton时，维护一下fa关系，将单词末尾存下来。
建完以后，把主串在Ac_automaton上跑一遍，把所有其能到达的节点打上标记，还是一样，遍历fail链，当发现有一个位置已经被标记过，那么其以上的fail（原谅我这不标准的措辞）一定被标记过了，可以节省时间。
最后从单词尾沿其父亲向上走，同时记录没有被标记节点个数cnt，碰到一个标记节点，直接跳出，len-cnt就是被标记，即出现最长的那个啦。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; char s[10000500],s1[100050][150]; int n,m; int fuction(char x){ switch(x){ case 'W': return 0; case 'S': return 1; case 'N': return 2; case 'E': return 3; } } struct Ac_automation{ struct node{ node *fail; node *son[4]; node *fa; int v; node(){ memset(this,0,sizeof(node)); } }; node *root; node *tail[100500]; void clear(){ root=new node(); } void insert(int num){ node *now=root; int l=strlen(s1[num]+1); for(int i=1;i<=l;i++){ int x=fuction(s1[num][i]); // cout<<"x="<<x<<" "; if(!now->son[x]) now->son[x]=new node(); // cout<<"PP"; // cout<<now->son[x]<<endl; now->son[x]->fa=now; now=now->son[x]; }tail[num]=now; } void generate(){ queue<node*>q; for(int i=0;i<4;i++) if(root->son[i]){ q.push(root->son[i]); root->son[i]->fail=root; }else root->son[i]=root; while(!q.empty()){ node *now=q.front(); q.pop(); for(int i=0;i<4;i++) if(now->son[i]){ q.push(now->son[i]); now->son[i]->fail=now->fail->son[i]; }else now->son[i]=now->fail->son[i]; } } void running(){ node *now=root; int l=strlen(s+1); for(int i=1;i<=l;i++){ int x=fuction(s[i]); now=now->son[x]; for(node *j=now;!j->v&&j!=root;j=j->fail) j->v=1; } } int query(int x){ int cnt=0; for(node *i=tail[x];i!=root;i=i->fa,cnt++) if(i->v)break; return strlen(s1[x]+1)-cnt; } }Acm; int main(){ scanf("%d%d",&n,&m); // cout<<"m="<<m<<endl; scanf("%s",s+1); Acm.clear(); for(int i=1;i<=m;i++){ scanf("%s",s1[i]+1); Acm.insert(i); // cout<<"i="<<i<<endl; } Acm.generate(); // cout<<"A"; Acm.running(); // cout<<"B"; for(int i=1;i<=m;i++) printf("%d ",Acm.query(i)); return 0; }
3、单词
由于我们建立Ac_automaton时会指出fail指针，fail指针一定指向以前“出现”过的节点，就和随机数据生成一颗树一样，把所有fail指针“倒”过来也会形成一棵树，我们称之为“fail树”。
这道题，我们建立Ac_automation，记录词尾，对每个插入节点权值++。然后统计fail树的子树和，词尾的sum值即是答案。
这样做的理由是，fail指向某个单词的最长后缀，即该单词为fail指向单词的“父串”，所以某个单词x出现在单词y中，则y的fail指针会指向x（这里仅仅是指后缀情况，非后缀情况可以转化为后缀情况），由于fail树把fail指针倒过来，求出子树和，就是该节点为末尾的单词出现的次数，因为我们把每个插入节点的贡献计算在内。
实现过程中，没有必要真的建出fail树，建Ac_automaton时，我们对trie进行bfs，对所有节点进行了拓扑逆序遍历，存下来倒着往上fail树和就好，因为一个节点的fail肯定在他之前入队。
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<stack> using namespace std; int n; char s[400][1000050]; struct Ac_automation{ struct node{ node *fail; node *son[26]; int sum; node(){ memset(this,0,sizeof(node)); } }; node *root; node *tail[400]; vector<node*>ans; int num; void clear(){ root=new node(); num=0; } void insert(int x){ node *now=root; int l=strlen(s[x]+1); for(int i=1;i<=l;i++){ if(!now->son[s[x][i]-'a']) now->son[s[x][i]-'a']=new node(); now=now->son[s[x][i]-'a']; now->sum++; }tail[x]=now; } void generate(){ queue<node*>q; for(int i=0;i<26;i++) if(root->son[i]){ root->son[i]->fail=root; q.push(root->son[i]); ans.push_back(root->son[i]); }else root->son[i]=root; while(!q.empty()){ node *now=q.front(); q.pop(); for(int i=0;i<26;i++) if(now->son[i]){ now->son[i]->fail=now->fail->son[i]; q.push(now->son[i]); ans.push_back(now->son[i]); }else now->son[i]=now->fail->son[i]; } } void handle(){ for(int i=ans.size()-1;i>=0;i--) ans[i]->fail->sum+=ans[i]->sum; } int query(int x){ return tail[x]->sum; } }Acm; int main(){ // freopen("word9.in","r",stdin); scanf("%d",&n); Acm.clear(); for(int i=1;i<=n;i++){ scanf("%s",s[i]+1); Acm.insert(i); } Acm.generate(); Acm.handle(); for(int i=1;i<=n;i++) printf("%d ",Acm.query(i)); return 0; }
4、病毒
就是找一个串，使之在Ac_automaton（Trie图）上不停地跑，可就是跑不到任何一个单词的结尾。这是环的特点。
我们对单词结尾打标记，因为fail指向的单词是该单词的后继，该单词出现，则该单词后继肯定出现，若后继结尾有标记，则该单词尾也应该别标记，否则该单词一旦出现，其有标记的后继也会出现，这是我们不希望看到的。标记完了以后判环，遇到标记节点直接continue因为我们不能到他，做完这些处理，如果还有环，那就TAK了。
判环的话用dfs加栈判断（有点像Tarjan？），当然，不用建栈，打个标记看在不在栈中就完事了。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<set> #include<map> using namespace std; int n; char s[40000]; bool flag; struct Ac_automaton{ struct node{ node *fail; node *son[2]; int v,ins,vist; node(){memset(this,0,sizeof(node));} }; node *root; void clear(){ root=new node(); } void insert(){ node *now=root; int l=strlen(s+1); // cout<<"l="<<l<<endl; for(int i=1;i<=l;++i){ // cout<<"s[i]="<<s[i]-'0'<<endl; if(!now->son[s[i]-'0']) now->son[s[i]-'0']=new node(); now=now->son[s[i]-'0']; }now->v=1; } void generate(){ queue<node*>q; for(int i=0;i<=1;i++) if(root->son[i]){ q.push(root->son[i]); root->son[i]->fail=root; }else root->son[i]=root; while(!q.empty()){ node *now=q.front(); q.pop(); for(int i=0;i<=1;i++) if(now->son[i]){ now->son[i]->fail=now->fail->son[i]; q.push(now->son[i]); now->son[i]->v|=now->son[i]->fail->v; }else now->son[i]=now->fail->son[i]; } } bool dfs(node *now){ now->ins=1; now->vist=1; for(int i=0;i<=1;i++){ node *nex=now->son[i]; if(nex->ins) return 1; if(nex->v) continue; if(nex->vist)continue; if(dfs(nex)) return 1; } now->ins=0; return 0; } }Acm; int main(){ scanf("%d",&n); Acm.clear(); for(int i=1;i<=n;i++){ scanf("%s",s+1); Acm.insert(); } Acm.generate(); Acm.dfs(Acm.root)?puts("TAK"):puts("NIE"); return 0; }
然后就可以去想想Ac_automaton上的dp啦（更加头疼）。