AC自动机为何,如何优化成Trie图:
匹配时因为每次都要跳fail边,复杂度上界可以达到 O(ml)
对于字符集{a,b,c}上的模式ab,aab,aaab,aaaab,ac和文本串aaaac,它们建出来的AC自动机和匹配过程是这样的(蓝色边是Trie树的边,红色边是fail指针,黄色边是匹配时的状态转移):
//对应AC自动机中的这一段;
while(j&&!tr[j][t]) j=ne[j];
if(tr[j][t]) j=tr[j][t];
如果失配时可以一步到位就好了。每次回溯的过程是固定的:一直跳,直到找到拥有儿子c的节点为止。因此无论什么时候在这个节点上失配,只要你找的是字符c,你总会在固定的节点上重新开始匹配。既然这样,不如直接把那个字符为c的节点变成自己的儿子,就可以省去回溯的麻烦:
构造方法:
//修改build函数
void build(){
for(int i=0;i<26;i++)
if(tr[0][i])
Q.push(tr[0][i]);
while(Q.size()){
int t=Q.front();
Q.pop();
int p=tr[t][i];
if(!p) tr[t][i]=tr[ne[t]][i];
else{
ne[p]=tr[ne[t]][i];
Q.push(p);
}
}
}
由于遍历到t点的时候t的儿子们的ne数组值已经更新过了,因此,必然可以一路递推到对应的子节点上
因为原本是DAG结构的AC自动机出现了环,因此称为Trie图,此时可以做到真正的O(m)
此外,相应的查询操作可以一步直接修改为:
for(int i=0,j=0;str[i];i++){
int t=str[i]-'a';
j=tr[j][t];
int p=j;
while(p){
res+=cnt[p];
cnt[p]=0;
p=ne[p];
}
}
参考:https://www.cnblogs.com/sclbgw7/p/9875671.html
2022.4.5 更新 ACAM板子(非动态开点/动态开点)
非动态开点:
#define N 200010
struct ACAM{
string s[N];
int q[N*30],hh,tt,idx,n;
int tr[N*30][26],dep[N*30],cnt[N*30],pos[N*30],fail[N*30];
int ans[N*30];
void insert(string &s,int id){
int p=0;
for(auto ch:s){
int u=ch-'a';
if(!tr[p][u]) tr[p][u]=++idx;
dep[tr[p][u]]=dep[p]+1;
p=tr[p][u];
}
pos[id]=p, cnt[p]++;
}
void get_fail(){
hh=0,tt=-1;
for(int i=0;i<26;++i)
if(tr[0][i]) q[++tt]=tr[0][i];
while(hh<=tt){
int p=q[hh++];
for(int i=0;i<26;++i){
if(tr[p][i]){
fail[tr[p][i]]=tr[fail[p]][i];
q[++tt]=tr[p][i];
}
else tr[p][i]=tr[fail[p]][i];
}
}
}
void build(){
cin >> n;rep(i,1,n) cin>>s[i];
for(int i=1;i<=n;++i) insert(s[i], i);
get_fail();
}
void match(string &t){
for(int i=0,p=0;i<t.size();++i){
p=tr[p][t[i]-'a'];
ans[p]++;
}
for(int i=idx-1;i>=0;--i) ans[fail[q[i]]]+=ans[q[i]];
}
void clear(){
for(int i=0;i<=idx;++i){
for(int j=0;j<26;++j){
ans[tr[i][j]]=pos[tr[i][j]]=dep[tr[i][j]]=cnt[tr[i][j]]=fail[tr[i][j]]=0;
tr[i][j]=0;
}
}
}
}AC;
动态开点版本
#define N 200010
struct ACAM{
struct Node{
int fail,ans;
int ch[26];
Node(int _fail=0,int _ans=0):
fail(_fail),ans(_ans){memset(ch,0,sizeof ch);};
};
string s[N];
vector<Node> tr;
int n,idx,q[N*30],hh,tt,pos[N*30];
void insert(string &s,int num){
if(!tr.size()) tr.push_back(Node(0,0));
int p=0;
for(auto ch:s){
int u=ch-'a';
if(tr[p].ch[u]==0){
tr[p].ch[u]=++idx;
tr.push_back(Node(0,0));
}
p=tr[p].ch[u];
}
pos[num]=p;
}
void get_fail(){
hh=0,tt=-1;
for(int i=0;i<26;++i)
if(tr[0].ch[i]) q[++tt]=tr[0].ch[i];
while(hh<=tt){
int u=q[hh++];
for(int i=0;i<26;++i){
if(tr[u].ch[i]){
tr[tr[u].ch[i]].fail=tr[tr[u].fail].ch[i];
q[++tt]=tr[u].ch[i];
}
else tr[u].ch[i]=tr[tr[u].fail].ch[i];
}
}
}
void build(){
cin >> n;
for(int i=1;i<=n;++i) cin>>s[i],insert(s[i],i);
get_fail();
}
void match(string &t){
int p=0;
for(auto ch:t){
p=tr[p].ch[ch-'a'];
tr[p].ans++;
}
for(int i=idx-1;i>=0;--i) tr[tr[q[i]].fail].ans+=tr[q[i]].ans;
}
void clear(){
for(int i=1;i<=n;++i) pos[i]=0;
tr.clear(); idx=n=0;
}
void print_ans(){
for(int i=1;i<=n;++i)
print(tr[pos[i]].ans);
}
}AC;
前面分析这个案例时只需要跳3次吧
wgg这里是不是有点并查集思想?
确实有点像路径压缩,其实更像求LCA那样求到当前点的时候所有之前的信息已经都被求出来了
就很神奇
优秀
nice!
哇巨佬太强了
Sora巨佬来评论我了耶 [拜一拜]