巨坑待填，还未施工完成，所以在洛谷的状态也是隐藏，请勿食用生肉！
AC自动机讲解超详细 - hyfhaha的博客 在模板题的题解区也可以找到这位大佬的身影。
AC 自动机 - OI Wiki 我的写法是在这学的。
AC自动机 多模式字串匹配
构建一个AC自动机分为三个步骤。
- 模式串插入建立trie树
- 构造对每一个节点构造fail指针
- 利用fail指针对主串进行匹配
插入trie树
inline void ins(char *s)
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
return ;
}
构造fail指针用BFS实现。注意fail指针的定义是当前节点为结尾的字符串的最长后缀能完全匹配的以根节点为开头的字符串。
构造时不断询问父亲的前缀指针是否有通过连接这条边相同的字符指向的儿子。
构造时无需实现，有点像并查集的路径压缩。
queue <int> q;
inline void build()
{
for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
} return ;
}
询问应题目而异。
询问模式串的总出现次数，对每一个结尾记录。用文本串在自动机上跑，每一个节点不断跳fail统计答案并销毁统计到的答案。方便以后不重复统计。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N=1e6+10;
namespace AC
{
int tr[N][40],tot,cnt[N],fail[N];
inline void ins(char s[])
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
cnt[u]++; return ;
}
queue <int> q;
inline void build()
{
for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
} return ;
}
inline int query(char s[])
{
int u=0,res=0;
for(int i=0;s[i];i++)
{
u=tr[u][s[i]-'a'];
for(int j=u;j && ~cnt[j];j=fail[j]) {res+=cnt[j]; cnt[j]=-1;}
}
return res;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int n;
char s[N];
scanf("%d",&n);
while(n--) {scanf(" %s",s); AC::ins(s);}
scanf(" %s",s);
AC::build();
printf("%d",AC::query(s));
// fclose(stdin); fclose(stdout);
return 0;
}
多组数据。
询问哪些模式串在文本串中出现得最多。
还是要跳fail，跳的时候对每一个以这个节点为结尾的字符串打上标记。
最后遍历每一个节点，如果是某个字符串的结尾则更新最大出现次数，以这个节点为结尾的模式串的出现次数映射到模式串上。遍历如果出现次数等于答案则输出。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
const int N=160,M=1e6+10;
namespace AC
{
const int sz=N*80;
int tot,tr[sz][40],fail[sz],idx[sz],val[sz],cnt[N];
inline void init()
{
memset(fail,0,sizeof(fail));
memset(tr,0,sizeof(tr));
memset(idx,0,sizeof(idx));
memset(cnt,0,sizeof(cnt));
memset(val,0,sizeof(val));
tot=0;
}
inline void ins(char s[],int id)
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
idx[u]=id;
}
queue <int> q;
inline void build()
{
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
}
}
inline int query(char t[])
{
int u=0,res=0;
for(int i=0;t[i];i++)
{
u=tr[u][t[i]-'a'];
for(int j=u;j;j=fail[j]) val[j]++;
}
for(int i=1;i<=tot;i++)
if(idx[i]) {res=max(res,val[i]); cnt[idx[i]]=val[i];}
return res;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int n;
char s[N][80],t[M];
while(scanf("%d",&n) == 1 && n)
{
AC::init();
for(int i=1;i<=n;i++) {scanf(" %s",s[i]); AC::ins(s[i],i);}
AC::build(); scanf(" %s",t);
int x=AC::query(t);
printf("%d\n",x);
for(int i=1;i<=n;i++)
if(AC::cnt[i] == x) printf("%s\n",s[i]);
}
// fclose(stdin); fclose(stdout);
return 0;
}
不保证模式串互不相同。
topo建图优化。
将fail指针理解为一条有向边，整个图是DAG。
遍历文本串后topo，一次性上传标记。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
const int N=2e5+10;
namespace AC
{
int tot,cnt[N],tr[N][40],fail[N],ans[N],in[N],pos[N],flag[N];
inline void ins(char s[],int id)
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
if(!flag[u]) flag[u]=id;
pos[id]=flag[u]; return ;
}
queue <int> q;
inline void build()
{
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; in[fail[tr[u][i]]]++; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
}
}
inline void topu()
{
int u;
for(int i=1;i<=tot;i++)
if(!in[i]) q.push(i);
while(!q.empty())
{
u=q.front(); q.pop();
ans[flag[u]]=cnt[u];
in[fail[u]]--;
cnt[fail[u]]+=cnt[u];
if(!in[fail[u]]) q.push(fail[u]);
} return ;
}
inline void query(char t[])
{
int u=0;
for(int i=0;t[i];i++)
cnt[u=tr[u][t[i]-'a']]++;
return ;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int n;
char s[N*10];
scanf("%d",&n);
for(int i=1;i<=n;i++) {scanf(" %s",s); AC::ins(s,i);}
AC::build(); scanf(" %s",s);
AC::query(s); AC::topu();
for(int i=1;i<=n;i++) printf("%d\n",AC::ans[AC::pos[i]]);
// fclose(stdin); fclose(stdout);
return 0;
}
应用
找前缀显然不好做，改成找子串。
用文本串在trie树上遍历跳fail打标记。
最后把每个模式串在trie树上遍历找最长前缀。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e7+10,M=1e5+10;
int n,m;
char s[N],t[M][110];
inline int turn(char c)
{
if(c == 'E') return 0;
if(c == 'S') return 1;
if(c == 'W') return 2;
return 3;
}
namespace AC
{
int tr[N][20],fail[N],cnt;
bool pre[N];
queue <int> q;
inline void ins(char str[])
{
int u=0;
for(int i=0,node;str[i];i++)
{
node=turn(str[i]);
if(!tr[u][node]) tr[u][node]=++cnt;
u=tr[u][node];
}
return ;
}
inline void build()
{
int u=0;
for(int i=0;i<4;i++) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
u=q.front(); q.pop();
for(int i=0;i<4;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
}
u=0;
for(int i=0;s[i];i++)
{
u=tr[u][turn(s[i])];
for(int i=u;i && !pre[i];i=fail[i]) pre[i]=true;
}
return ;
}
inline int query(char str[])
{
int u=0,res=0;
for(int i=0;str[i];i++)
{
u=tr[u][turn(str[i])];
if(pre[u]) res=i+1;
}
return res;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
scanf("%d%d %s",&n,&m,s);
for(int i=1;i<=m;i++)
{
scanf(" %s",t[i]);
AC::ins(t[i]);
}
AC::build();
for(int i=1;i<=m;i++) printf("%d\n",AC::query(t[i]));
// fclose(stdin); fclose(stdout);
return 0;
}
找一个无限长的文本串使得所有模式串没有出现过。
在trie树上找不存在标记的环。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 3e4+10;
namespace AC
{
int cnt,tr[N][10],fail[N];
bool virus[N],hopeless[N],vis[N];
queue <int> q;
inline void ins(char *s)
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'0']) tr[u][s[i]-'0']=++cnt;
u=tr[u][s[i]-'0'];
}
virus[u]=true; return ;
}
inline void build()
{
int u;
if(tr[0][0]) q.push(tr[0][0]);
if(tr[0][1]) q.push(tr[0][1]);
while(!q.empty())
{
u=q.front(); q.pop();
if(tr[u][0])
{
fail[tr[u][0]]=tr[fail[u]][0];
q.push(tr[u][0]);
virus[tr[u][0]]|=virus[tr[fail[u]][0]];//前缀是病毒自己一定不行
}
else tr[u][0]=tr[fail[u]][0];
if(tr[u][1])
{
fail[tr[u][1]]=tr[fail[u]][1];
q.push(tr[u][1]);
virus[tr[u][1]]|=virus[tr[fail[u]][1]];
}
else tr[u][1]=tr[fail[u]][1];
}
return ;
}
bool dfs(int u)
{
vis[u]=true;
if(vis[tr[u][0]] || vis[tr[u][1]]) return true;//找到环
if(!virus[tr[u][0]] && !hopeless[tr[u][0]])
{//探索过的一定无解，不再探索
hopeless[tr[u][0]]=true;
if(dfs(tr[u][0])) return true;
}
if(!virus[tr[u][1]] && !hopeless[tr[u][1]])
{
hopeless[tr[u][1]]=true;
if(dfs(tr[u][1])) return true;
}
return vis[u]=false;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
int n;
char s[N];
scanf("%d",&n);
while(n--)
{
scanf(" %s",s);
AC::ins(s);
}
AC::build();
if(AC::dfs(0)) printf("TAK");
else printf("NIE");
// fclose(stdin); fclose(stdout);
return 0;
}
栈式匹配
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e5+10;
namespace AC
{
int fail[N],tr[N][40],siz[N],cnt=0,top=0,pos[N],last[N];
queue <int> q;
inline void ins(char s[])
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'a']) tr[u][s[i]-'a']=++cnt;
u=tr[u][s[i]-'a'];
}
siz[u]=strlen(s); return ;
}
inline void build()
{
int u;
for(int i=0;i<26;i++) if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
} return ;
}
inline void work(char s[])
{
int u=0;
for(int i=0;s[i];i++)
{
last[++top]=u=tr[u][s[i]-'a'];
pos[top]=i;
if(siz[u]) {top-=siz[u]; u=last[top];}
}
return ;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
char s[N],t[N];
int n;
scanf(" %s%d",s,&n);
while(n--)
{
scanf(" %s",t);
AC::ins(t);
}
AC::build(); AC::work(s);
for(int i=1;i<=AC::top;i++) printf("%c",s[AC::pos[i]]);
// fclose(stdin); fclose(stdout);
return 0;
}
AC自动机上DP。
把所有小串插入AC自动机。
对于AC自动机的节点，计算出根到每个节点是否会经过至少一个小串。
$f_{0/1,n,x}$ 表示是否经过至少一个小串，当前构造的串长，当前在x节点上。
首先计算出 $cnt_x$ 表示从根到x的路径上是否经过至少一个小串。这个可以在BFS的时候计算。
考虑如何转移。
对于26条出边 $x->tr[x][k]$ 记 y=tr[x][k]。
$\text f[v\ |\ cnt[y]\ ][n+1][y]+=f[v][n][y]$
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N=6e3+10,p=1e4+7;
int n,m;
namespace AC
{
int tot=0,cnt[N],tr[N][40],fail[N],f[2][110][N];
inline void ins(char s[])
{
int u=0;
for(int i=0;s[i];i++)
{
if(!tr[u][s[i]-'A']) tr[u][s[i]-'A']=++tot;
u=tr[u][s[i]-'A'];
}
cnt[u]=1;
}
queue <int> q;
inline void build()
{
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty())
{
int u=q.front(); q.pop();
cnt[u]|=cnt[fail[u]];
for(int i=0;i<26;i++)
if(tr[u][i]) {fail[tr[u][i]]=tr[fail[u]][i]; q.push(tr[u][i]);}
else tr[u][i]=tr[fail[u]][i];
}
}
inline int dp()
{
f[0][0][0]=1;
for(int i=0;i<m;i++)
for(int o=0;o<2;o++)
for(int j=0;j<=tot;j++)
if(f[o][i][j])//常数优化
for(int k=0,x;k<26;k++)
{
x=tr[j][k];
f[o|cnt[x]][i+1][x]=(f[o|cnt[x]][i+1][x]+f[o][i][j])%p;
}
int res=0;
for(int i=0;i<=tot;i++) res=(res+f[1][m][i])%p;
return res;
}
}
int main()
{
// freopen("work.in","r",stdin); freopen("work.out","w",stdout);
char s[110];
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {scanf(" %s",s); AC::ins(s);}
AC::build();
printf("%d",AC::dp());
// fclose(stdin); fclose(stdout);
return 0;
}
待填。
