学习博客：https://www.cnblogs.com/hyfhaha/p/10802604.html

AC自动机可以认为是kmp+trie树。

trie树数组大小是字符串数目n*最大字符串长度mxl;

AC自动机中主要是fail数组，fail数组与kmp中的PMT意义类似。

更详细讲解；https://www.cnblogs.com/hyfhaha/p/10802604.html

1.给出若干单词，和一个字符串，求字符串中出现次数最多的单词。

模板题

#include<bits/stdc++.h> #define N 11000 #define ll long long using namespace std; struct nd{ int son[26],fail,flag; }tr[N]; int vis[N],cnt=1; void ins(char s[],int id){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int v=s[i]-'a'; if(tr[o].son[v]==0)tr[o].son[v]=++cnt; o=tr[o].son[v]; } tr[o].flag=id; } queue<int>q; void getfail(){ for(int i=0;i<26;i++)tr[0].son[i]=1; q.push(1);tr[1].fail=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=tr[x].fail; for(int i=0;i<26;i++){ int y=tr[x].son[i]; if(y==0){ tr[x].son[i]=tr[fx].son[i];continue; } tr[y].fail=tr[fx].son[i]; q.push(y); } } } void query(char s[]){ int ls=strlen(s),o=1; for(int i=0;i<ls;i++){ int v=s[i]-'a'; int k=tr[o].son[v]; while(k>1){ if(tr[k].flag)vis[tr[k].flag]++; k=tr[k].fail; } o=tr[o].son[v]; } } char s[155][75]; char s1[1000100]; int n; int main(){ while(scanf("%d",&n)){ if(n==0)break; cnt=1;memset(tr,0,sizeof(tr)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ scanf("%s",s[i]); ins(s[i],i); } scanf("%s",s1); getfail(); query(s1); int ans=0; for(int i=1;i<=n;i++)ans=max(ans,vis[i]); printf("%d\n",ans); for(int i=1;i<=n;i++)if(ans==vis[i])printf("%s\n",s[i]); } return 0; }

2.给出若干单词，和一个字符串，求出每个单词在字符串中出现次数。

分析：每次暴力跳fail树很容易超时，不在每次暴力跳，x向fail[x]建边，建完后是一个DAG,然后一次性统计答案

#include<bits/stdc++.h> #define N 200010 #define ll long long using namespace std; struct nd{ int son[26],fail; }tr[N*30]; int vis[N*30],cnt=1,v[N*30],du[N*30]; void ins(char s[],int id){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int v=s[i]-'a'; if(tr[o].son[v]==0)tr[o].son[v]=++cnt; o=tr[o].son[v]; } vis[id]=o; } queue<int>q; void getfail(){ for(int i=0;i<26;i++)tr[0].son[i]=1; q.push(1);tr[1].fail=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=tr[x].fail; for(int i=0;i<26;i++){ int y=tr[x].son[i]; if(y==0){ tr[x].son[i]=tr[fx].son[i];continue; } tr[y].fail=tr[fx].son[i]; du[tr[y].fail]++; q.push(y); } } } void query(char s[]){ int ls=strlen(s),o=1; for(int i=0;i<ls;i++){ int vx=s[i]-'a'; o=tr[o].son[vx]; v[o]++; } } char s[N*10]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); ins(s,i); } scanf("%s",s); getfail(); query(s); while(!q.empty())q.pop(); for(int i=1;i<=cnt;i++)if(!du[i])q.push(i); while(!q.empty()){ int x=q.front();q.pop(); int y=tr[x].fail; v[y]+=v[x]; if(--du[y]==0)q.push(y); } for(int i=1;i<=n;i++)printf("%d\n",v[vis[i]]); return 0; }

3.P2444 [POI2000]病毒

题目描述

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 {011,11,00000} 为病毒代码段，那么一个可能的无限长安全代码就是 010101......010101…如果{01,11,000000} 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码

分析：

正着很难分析能否构造出安全代码，可以假设有一安全代码S,则在ac自动机上并不会有任何字符串被匹配到。因为S无限长，想想AC自动机的匹配过程，当trie树+fail建图（并不用x向fail[x]连边）中存在环，则说明存在安全代码。

所以只要建好图，然后判断是否存在一个不经过字符串末尾的环。

#include<bits/stdc++.h> #define N 30010 #define ll long long using namespace std; int tr[N*200][2],fail[N*200],ed[N*200]; int vis[N*200],cnt=1,n; void ins(char s[]){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=s[i]-'0'; if(!tr[o][t])tr[o][t]=++cnt; o=tr[o][t]; } ed[o]=1; } queue<int>q; void getfail(){ for(int i=0;i<=1;i++)tr[0][i]=1; q.push(1);fail[1]=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<=1;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i]; q.push(y); if(ed[fail[y]])ed[y]=1; } } } int dfs(int x){ vis[x]=0; for(int i=0;i<=1;i++){ int t=tr[x][i]; if(ed[t])continue; if(vis[t]==0)return 1; else if(vis[t]==-1){ if(dfs(t))return 1; } } vis[x]=1; return 0; } char s[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s); ins(s); } getfail(); memset(vis,-1,sizeof(vis)); if(dfs(1))printf("TAK"); else printf("NIE"); return 0; }

4.P2292 [HNOI2004]L语言

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 TT 是由若干小写字母构成。一个单词 WW 也是由若干小写字母构成。一个字典 DD 是若干个单词的集合。我们称一段文章 TT 在某个字典 DD 下是可以被理解的，是指如果文章 TT 可以被分成若干部分，且每一个部分都是字典 DD 中的单词。

例如字典 D中包括单词 is,name,what,your，则文章whatisyourname 是在字典 D 下可以被理解的，因为它可以分成 4 个单词：what,is,your,name，且每个单词都属于字典 D，而文章 whatisyouname 在字典 D 下不能被理解，但可以在字典 D′=D∪{you} 下被理解。这段文章的一个前缀whatis，也可以在字典 D 下被理解，而且是在字典 D 下能够被理解的最长的前缀。

给定一个字典 D，你的程序需要判断若干段文章在字典 D 下是否能够被理解。并给出其在字典 D 下能够被理解的最长前缀的位置。

分析：

先跑一边ac自动机，求出可以匹配的末尾节点和字符串长度，然后dp一下，if(f[i-len])f[i]=1;不过题目加强以后数据太强，感觉线性做法还需在优化（或卡常）才可以过去。

#include<bits/stdc++.h> #define N 2000010 #define ll long long using namespace std; int tr[210][26],fail[210],dep[210],ed[210],cnt=1; char s[N]; int n,m,f[N]; inline void ins(char *s){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=s[i]-'a'; if(!tr[o][t])tr[o][t]=++cnt; dep[tr[o][t]]=dep[o]+1; o=tr[o][t]; } ed[o]=1; } queue<int>q; void getfail(){ for(int i=0;i<26;i++)tr[0][i]=1; fail[1]=0;q.push(1); while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<26;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i]; continue; } fail[y]=tr[fx][i]; q.push(y); } } } inline int query(char *s){ int o=1,ls=strlen(s); for(register int i=0;i<ls;++i)f[i]=0; int ans=-1; for(register int i=0;i<ls;++i){ int t=s[i]-'a'; int k=tr[o][t]; while(k>1){ if(ed[k]){ //cout<<i<<" "<<dep[k]<<endl; if(i-dep[k]==-1)f[i]=1; else if(f[i-dep[k]])f[i]=1; } k=fail[k]; } o=tr[o][t]; if(f[i])ans=i; } return ans+1; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s); ins(s); } dep[1]=0; getfail(); while(m--){ scanf("%s",s); printf("%d\n",query(s)); } return 0; }

P3121 [USACO15FEB]Censoring G

题目链接：https://www.luogu.com.cn/problem/P3121

维护一个栈，记录当前走到了字典树中的那个位置，删除的时候跳回即可。

#include<bits/stdc++.h> #define N 100010 #define ll long long using namespace std; char s[N],tmps[20*N]; int tr[N*20][26],fail[N*20],ed[N*20],sta[N],cnt=1; bool vis[N]; void ins(char *s){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=s[i]-'a'; if(!tr[o][t])tr[o][t]=++cnt; o=tr[o][t]; } ed[o]=ls; } queue<int>q; void getfail(){ for(int i=0;i<26;i++)tr[0][i]=1; q.push(1);fail[1]=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<26;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i]; q.push(y); } } } int n,f[N]; int main(){ scanf("%s",s); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",tmps); ins(tmps); } getfail(); int o=1,top=0,ls=strlen(s); sta[++top]=1; int topf=0,bo=0; for(int i=0;i<ls;i++){ int t=s[i]-'a'; int k=tr[o][t]; bo=0; sta[++top]=k; f[++topf]=i; if(k>1){ if(ed[k]){ int len=ed[k]; topf-=len; top-=len; o=sta[top];bo=1; } } if(bo==0) o=tr[o][t]; } for(int i=1;i<=topf;i++)printf("%c",s[f[i]]); return 0; }

P4045 [JSOI2009]密码

题目链接：https://www.luogu.com.cn/problem/P4045

状压+AC自动机。

f[i][x][j]表示前i个字符，对模式串的覆盖状态为x,走到字典树上的j点,的方案树。

所以f[i+1][x|v[k]][k]=f[i][x][j].k是j的子节点。对于输出方案，因为方案数<=42,所以不会出现一个取任意字符的位置，否则，他可以在第一位或最后一位，答案是52.所以方案是模式串的排列，直接暴力排列，注意两个串后缀和前缀相同的情况。

#include<bits/stdc++.h> #define N 30010 #define ll long long using namespace std; int n,m,tr[N][26],fail[N],v[N],cnt=1; ll f[26][1025][105]; string anss[100]; void ins(char *s,int id){ int o=1,ls=strlen(s); for(int i=0;i<ls;++i){ int t=s[i]-'a'; if(!tr[o][t])tr[o][t]=++cnt; o=tr[o][t]; } v[o]|=1<<id; } queue<int>q; void getfail(){ for(int i=0;i<26;i++)tr[0][i]=1; q.push(1);fail[1]=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<26;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i]; q.push(y); } } } char s[20][N]; char c[N*2],s1[20][N]; int a[20],b[20][20]; int calc(char *s,char *t){ int ls=strlen(s),lt=strlen(t); for(int len=min(ls,lt);len>=0;len--){ int bo=0; for(int i=0;i<len;i++){ if(t[i]!=s[ls-len+i])bo=1; } if(bo==0)return len; } } int pd(char *s,char *t){ int ls=strlen(s),lt=strlen(t); for(int i=0;i+ls-1<lt;i++){ int bo=0; for(int j=0;j<ls;j++){ if(s[j]!=t[i+j])bo=1; } if(bo==0)return 1; }return 0; } int vis[1000]; int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++){ scanf("%s",s[i]); ins(s[i],i-1); } getfail(); for(int i=2;i<=cnt;i++){ for(int j=i;j>1;j=fail[j])v[i]|=v[j]; } memset(f,0,sizeof(f)); f[0][0][1]=1; for(int i=0;i<m;i++){ for(int x=0;x<(1<<n);x++){ for(int j=1;j<=cnt;j++){ if(f[i][x][j]==0)continue; for(int k=0;k<=25;k++){ f[i+1][x|v[tr[j][k]]][tr[j][k]]+=f[i][x][j]; } } } } ll ans=0; for(int i=1;i<=cnt;i++){ ans+=f[m][(1<<n)-1][i]; } printf("%lld",ans); if(ans<=42){ printf("\n"); /*for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i!=j&&pd(s[i],s[j]))vis[i]=1; } int t=n; n=0; for(int i=1;i<=t;i++)if(vis[i]==0){ int ls=strlen(s[i]);n++; for(int j=0;j<ls;j++)s1[n][j]=s[i][j]; } for(int i=1;i<=n;i++){ int ls=strlen(s1[i]); for(int j=0;j<ls;j++)s[i][j]=s1[i][j]; }*/ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)b[i][j]=calc(s[i],s[j]); for(int i=1;i<=n;i++)a[i]=i; int tot=0; do{ int top=0; for(int i=1;i<=n;i++){ int ls=strlen(s[a[i]]); for(int j=b[a[i-1]][a[i]];j<ls;j++)c[++top]=s[a[i]][j]; } if(top==m){ tot++; for(int i=1;i<=top;i++)anss[tot]+=c[i]; } }while(next_permutation(a+1,a+n+1)); sort(anss+1,anss+tot+1); for(int i=1;i<=tot;i++){ cout<<anss[i]<<endl; } } }

P5231 [JSOI2012]玄武密码

题目链接：https://www.luogu.com.cn/problem/P5231

直接跑一边AC自动机就行

#include<bits/stdc++.h> #define N 10000010 #define ll long long using namespace std; char s[N],s1[110]; int tr[N][4],fail[N],cnt=1; bool a[N]; vector<int>v[100010]; int get(char ch){ if(ch=='E')return 0; else if(ch=='S')return 1; else if(ch=='W')return 2; else return 3; } void ins(char *s,int id){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=get(s[i]); if(!tr[o][t])tr[o][t]=++cnt; o=tr[o][t];v[id].push_back(o); } } queue<int>q; void getfail(){ for(int i=0;i<=3;i++)tr[0][i]=1; fail[1]=0;q.push(1); while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<=3;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i];q.push(y); } } } int n,m; int main(){ scanf("%d%d",&n,&m); scanf("%s",s); for(int i=1;i<=m;i++){ scanf("%s",s1); ins(s1,i); } getfail(); int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=get(s[i]); int k=tr[o][t]; while(k>1){ a[k]=1;k=fail[k]; } o=tr[o][t]; } for(int i=1;i<=m;i++){ int lv=v[i].size(),bo=0; for(int j=lv-1;j>=0;j--){ if(a[v[i][j]]){ printf("%d\n",j+1);bo=1;break; } } if(!bo)printf("0\n"); } return 0; }

P2414 [NOI2011]阿狸的打字机

题目链接：https://www.luogu.com.cn/problem/P2414。

dfs序，树状数组，离线。

比较综合的一道题。先根据题目给的字符串建立tire树，然后对于询问（x,y），答案是rt->ed[y]中通过跳fail可以到达ed[x]的节点数。直接暴力跳是40.然后离线，将y相同的一次性处理。这是70.

询问（x,y）也可以看成在fail树中，ed[x]的子树中有多少在tire中属于rt->ed[y]，这样离线同样是70

利用dfs的性质（深度优先，每次都是一条链），在tire上dfs，当进入时+1,离开时-1，利用树状数组与dfs序求出子树和。

#include<bits/stdc++.h> #define eps 1e-7 #define ll long long #define N 100010 #define md 20000311 using namespace std; int cnt=1,n=0,m,fail[N],tr[N][26],ed[N],c[N],ans[N],f[N],sta[N]; struct nd{ int x,y; }a[N]; struct qnd{ int x,id; }; vector<qnd>va[N]; vector<int>vec[N]; char s[N]; queue<int>q; int low[N],dfn[N],tim=0,ay[N],vis[N][26]; void getfail(){ for(int i=0;i<26;i++)tr[0][i]=1; q.push(1);fail[1]=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; for(int i=0;i<26;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i]; q.push(y); } } } int cmp(nd xx,nd yy){ return xx.y<yy.y; } int fed[N]; void dfs(int x){ dfn[x]=++tim; int lenv=vec[x].size(); for(int i=0;i<lenv;i++){ dfs(vec[x][i]); } low[x]=tim; } int lo(int x){ return x&-x; } void upd(int x,int v){ while(x<=tim){ c[x]+=v;x+=lo(x); } } int sum(int x){ int ret=0; while(x){ ret+=c[x];x-=lo(x); } return ret; } void dfst(int x){ upd(dfn[x],1); if(ay[x]){ int t=va[x].size(); for(int i=0;i<t;i++){ qnd tmp=va[x][i]; ans[tmp.id]=sum(low[tmp.x])-sum(dfn[tmp.x]-1); } } for(int i=0;i<26;i++){ if(vis[x][i])dfst(tr[x][i]); } upd(dfn[x],-1); } int main(){ scanf("%s",s); int ls=strlen(s); int o=1,top=0; sta[++top]=1; for(int i=0;i<ls;i++){ if(s[i]=='P')ed[o]=++n,fed[n]=o; else if(s[i]=='B'){ top--;o=sta[top]; } else{ int t=s[i]-'a'; if(!tr[o][t])vis[o][t]=1,tr[o][t]=++cnt; f[tr[o][t]]=o; o=tr[o][t];sta[++top]=o; } } scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d%d",&a[i].x,&a[i].y); ay[fed[a[i].y]]=1; va[fed[a[i].y]].push_back((qnd){fed[a[i].x],i}); } getfail(); for(int i=1;i<=cnt;i++)vec[fail[i]].push_back(i); dfs(1); dfst(1); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }

P3041 [USACO12JAN]Video Game G

题目链接：https://www.luogu.com.cn/problem/P3041

AC自动机上的经典dp做法。

f[i][j]表示前i个字符，在tire上走到了j点,所含有最多的模式串。

f[i+1][k]=max(f[i+1][k],f[i][j]+ed[k])(别忘了取max)，k=son[j],ed[k]是以k为末尾的模式串个数.

#include<bits/stdc++.h> #define N 100010 #define ll long long using namespace std; char s[N]; int cnt=1,n,m; ll fail[N],tr[N][3],f[1010][1010],ed[N]; void ins(char *s){ int o=1,ls=strlen(s); for(int i=0;i<ls;i++){ int t=s[i]-'A'; if(!tr[o][t])tr[o][t]=++cnt; o=tr[o][t]; } ed[o]++; } queue<int>q; void getfail(){ for(int i=0;i<3;i++)tr[0][i]=1; q.push(1);fail[1]=0; while(!q.empty()){ int x=q.front();q.pop(); int fx=fail[x]; ed[x]+=ed[fx]; for(int i=0;i<3;i++){ int y=tr[x][i]; if(!y){ tr[x][i]=tr[fx][i];continue; } fail[y]=tr[fx][i]; q.push(y); } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",s); ins(s); } getfail(); memset(f,-1,sizeof(f)); f[0][1]=0; for(int i=0;i<m;i++){ for(int j=1;j<=cnt;j++){ if(f[i][j]==-1)continue; for(int k=0;k<3;k++){ f[i+1][tr[j][k]]=max(f[i+1][tr[j][k]],f[i][j]+ed[tr[j][k]]); } } } ll ans=0; for(int i=1;i<=cnt;i++)ans=max(ans,f[m][i]); printf("%lld",ans); return 0; }