AC自动机学习笔记
AC自动机简介
自动机的一种,著名的多模匹配算法
可以理解为 Trie + KMP
结构
建立在字典树的基础上
先把所有要匹配的模式串全部塞到一个字典树上面
然后在上面添加一种指针
类似于 KMP 中的 nxt[] 数组,AC自动机中的每个节点有一个叫做 fail 的指针(失配指针)
与 KMP 类似,
fail 表示最长的相等前后缀,只不过不是一个字符串上面考虑,而是在整棵字典树上面考虑
fail就是从后缀的结尾指向前缀的结尾
举个例子
这张图是
she shr say her he
这五个字符串构建出来的AC自动机 红色的是 fail
来看一眼左下角的那个点
他表示的字符串是 she
有一个后缀 he 正好是 her 的前缀,所以这个点就要指向 her 的‘e’
其余同理
(根节点的 fail 指向自己)
构建过程
求 fail[i] 需要用到比 i 深度小的所有点
因此使用 深度优先搜索
当前考虑到了节点 u 他的父亲是 p 通过字符 c 转移而来
即 \(tr[p][c]=u\)
如果 tr[fail[p],c] 存在 则让 u 的 fail 指针指向 tr[fail[p],c]
否则一直往上跳(tr[fial[fail[p]],c],tr[fail[fail[fail[p]]],c], ...)实在找不到存在的就到根节点为止
代码
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++)
{
int v=tr[u][i];
if(!v) tr[u][i]=tr[nxt[u]][i];
else
{
nxt[v]=tr[nxt[u]][i];
q.push(v);
}
}
}
}
这里代码跟思路有点小不一样是因为加了个优化
变成了trie图
原本要一直往上跳 这回路径压缩
直接一跳到底
板子
例题链接:
Code:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+5,M=1e6+5,S=55;
int tr[N*S][26],cnt[N*S],idx;
queue<int> q;
string str;
int nxt[N*S];
int n;
void insert()
{
int u=0;
for(int i=0;str[i];i++)
{
int v=str[i]-'a';
if(!tr[u][v])
tr[u][v]=++idx;
u=tr[u][v];
}
cnt[u]++;
}
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++)
{
int v=tr[u][i];
if(!v) tr[u][i]=tr[nxt[u]][i];
else
{
nxt[v]=tr[nxt[u]][i];
q.push(v);
}
}
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(tr,0,sizeof(tr));
memset(cnt,0,sizeof(cnt));
memset(nxt,0,sizeof(nxt));
idx=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>str;
insert();
}
build();
cin>>str;
int ans=0;
for(int i=0,j=0;str[i];i++)
{
int t=str[i]-'a';
j=tr[j][t];
int p=j;
while(p)
{
ans+=cnt[p];
cnt[p]=0;
p=nxt[p];
}
}
cout<<ans<<endl;
}
return 0;
}
明人不说暗话,其实AC自动机还有点没搞明白
需要再钻研
赶紧接着学习去了
钻研透彻了就更新修改一下
byebye
参考:AcWing算法提高课 OI Wiki
标签:AC,int,tr,str,fail,自动机 From: https://www.cnblogs.com/Orange-Star/p/16609162.html