柒葉灬 的博客

柒葉灬 的博客

AC自动机总结(个人笔记)

posted on 2018-12-31 21:41:00 | under 专题总结 |

AC自动机总结


前置技能: $kmp$ 算法, $Tire$ 树。

AC自动机和 $Tire$ 树一样,不做重复的运算,所以也有一个 $nxt$ 数组,即在匹配失败的时候快速跳到最长后缀位置。

模板:

void insert(char *str){
    int x=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int &pos=son[x][str[i]-'a'];
        if(!pos)pos=++tot;
        x=pos;
    }
}
void Getnxt(){
    queue<int>q;
    for(int i=0;i<26;i++)
        if(son[0][i])q.push(son[0][i]);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(son[x][i]){
                nxt[son[x][i]]=son[nxt[x]][i];//A
                q.push(son[x][i]);
            }else son[x][i]=son[nxt[x]][i];//B
    }
}

为什么A的位置不需要一直跳了呢?,因为如果 $nxt[x]$ 已经是前面的最佳匹配,

此时若 $nxt[x]$ 有 $i$ ,则最佳后缀肯定指向 $son[nxt[x]][i]$ ,

否则需要向上跳,而B的位置已经处理出来了,所以仍然是 $son[nxt[x]][i]$


入门题目:专题A


初学题目:专题B

注意AC自动机是以询问的串建的,不是以目标串建的。

写了这道题目就很清楚了


专题D

由于要判断是否重叠,所以需要记录出现的位置,用vector存就行了,防止一样的串一直询问,所以dp一下就行了。


专题F

AC自动机+DP

一道很好的题目,注意用AC自动机匹配一定不能 先出不合法 后去除,这样子会错。


专题G

AC自动机+状压DP


专题J

AC自动机+矩阵乘法(矩阵快速幂)

技巧:看到状态转移类型,切转移次数有 $10^9$ 这么大肯定是矩阵快速幂


专题N

这题需要把fail树拉出来了,这里写的是可持久化线段树,在线,(听说还有离线的线段树合并)。

因为需要找最长前缀后缀,所以要从前面一个字符串的位置一直跳nxt数组,

直到跳到了有被后面一个字符串覆盖的节点,则那个节点的深度就是答案,

用可持久化线段树动态开点插入就行了。

代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5;
bool cur1;
int n,m,a,b;
int tot,to[maxn],dep[maxn],nxt[maxn],son[maxn][4];
char str[maxn];
vector<int>T[maxn];
struct SegTree{
    static const int maxm=maxn*22;
    int tot,rt[maxn],lson[maxm],rson[maxm],val[maxm];
    void clear(){
        tot=0;
        memset(rt,0,sizeof(rt));
        memset(lson,0,sizeof(lson));
        memset(rson,0,sizeof(rson));
    }
    void insert(int &rt,int od,int l,int r,int x,int pos){
        rt=++tot;
        if(l==r){
            val[rt]=pos;
            return;
        }
        lson[rt]=lson[od];
        rson[rt]=rson[od];
        int mid=l+r>>1;
        if(x<=mid)insert(lson[rt],lson[od],l,mid,x,pos);
        else insert(rson[rt],rson[od],mid+1,r,x,pos);
    }
    int Query(int rt,int l,int r,int x){
        if(!rt)return -1;
        if(l==r)return val[rt];
        int mid=l+r>>1;
        if(x<=mid)return Query(lson[rt],l,mid,x);
        else return Query(rson[rt],mid+1,r,x);
    }
    int solve(int a,int b){
        return Query(rt[to[a]],1,n,b)+1;
    }
    void add(int a,int x,int pos){
        insert(rt[a],rt[a],1,n,x,pos);
    }
    void Give(int a,int b){
        rt[a]=rt[b];
    }
}S;
void insert(char *str,int p){
    int x=0;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]=='T')str[i]='B';
        else if(str[i]=='G')str[i]='D';

        int &pos=son[x][str[i]-'A'];
        if(!pos){
            pos=++tot;
            dep[pos]=i;
        }
        x=pos;
        T[x].push_back(p);
    }
    to[p]=x;
}
void update(int y){
    for(int j=0;j<T[y].size();j++){
        S.add(y,T[y][j],dep[y]);
    }
}
void Getnxt(){
    queue<int>q;
    for(int i=0;i<4;i++)
        if(son[0][i]){
            update(son[0][i]);
            q.push(son[0][i]);
        }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<4;i++)
            if(son[x][i]){
                int y=son[x][i];
                nxt[y]=son[nxt[x]][i];

                S.Give(y,nxt[y]);
                update(y);
                q.push(y);
            }else son[x][i]=son[nxt[x]][i];
    }
}
void clear(){
    for(int i=0;i<=tot;i++)
        T[i].clear();
    memset(nxt,0,sizeof(nxt));
    memset(son,0,sizeof(son));
    tot=0;
    S.clear();
}
bool cur2;
int main(){
//  double sz=&cur2-&cur1;
//  cout<<sz/1024<<endl;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%s",str);
            insert(str,i);
        }
        dep[0]=-1;
        Getnxt();
        while(m--){
            scanf("%d%d",&a,&b);
            printf("%d\n",S.solve(a,b));
        }
        clear();
    }
    return 0.0;
}

专题O

进阶题目:把fail树拉出来重新建一颗树。

设第x个单词为最后的最大贡献为 $f(x)$ 则答案肯定是 $f(x)=A[x]+max(f(i))$ 。

所以只要得到 $max(f(i))$ 就行了

所取的 $f(i)$ 中,i是x的子串

我们知道,若第 $i$ 个单词是第 $x$ 个单词的子串,则 $x$ 字符串中必定有一个位置通过nxt可以跳到 $i$ 单词的末尾。

我们只要维护这个就行了。

我们把fail树拉出来,每次把答案加到末尾节点,变成了修改子树最大值问题了。

代码:

#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=2e4+5,maxm=3e5+5;
bool cur1;
int n,A[maxn],to[maxn];
int tot;
int fa[maxm];
int nxt[maxm];
int son[maxm][26];
char str[maxm];

struct Graph{
    int id,to[maxm],nxt[maxm],head[maxm];
    void add_edge(int u,int v){
        to[++id]=v;
        nxt[id]=head[u];
        head[u]=id;
    }
}G;
struct SegTree{
    struct node{
        int l,r,mx,lazy;
        void tomax(int x){
            mx=max(mx,x);
            lazy=max(lazy,x);
        }
    }tree[maxm<<2];
    void up(int p){
        tree[p].mx=max(tree[p<<1].mx,tree[p<<1|1].mx);
    }
    void down(int p){
        int &pos=tree[p].lazy;
        if(pos){
            tree[p<<1].tomax(pos);
            tree[p<<1|1].tomax(pos);
            pos=0;
        }
    }
    int id,L[maxm],R[maxm];
    void dfs(int x){
        L[x]=++id;
        for(int i=G.head[x];i;i=G.nxt[i])
            dfs(G.to[i]);
        R[x]=id;
    }
    void build(int l,int r,int p){
        tree[p]=(node){l,r,0,0};
        if(l==r)return;
        int mid=l+r>>1;
        build(l,mid,p<<1);
        build(mid+1,r,p<<1|1);
    }
    void update(int l,int r,int pos,int p){
        if(tree[p].l==l&&tree[p].r==r)
            return tree[p].tomax(pos);
        down(p);
        int mid=tree[p].l+tree[p].r>>1;
        if(r<=mid)update(l,r,pos,p<<1);
        else if(l>mid)update(l,r,pos,p<<1|1);
        else {
            update(l,mid,pos,p<<1);
            update(mid+1,r,pos,p<<1|1);
        }
        up(p);
    }
    int Query(int x,int p){
        if(tree[p].l==tree[p].r)
            return tree[p].mx;
        down(p);
        int mid=tree[p].l+tree[p].r>>1;
        if(x<=mid)return Query(x,p<<1);
        else return Query(x,p<<1|1);
    }
    void Build(){
        id=0;
        dfs(0);
        build(1,id,1);
    }
    void add(int a){
        update(L[to[a]],R[to[a]],A[a],1);
    }
    int solve(int a){
        int mx=0,x=to[a];
        while(x){
            mx=max(mx,Query(L[x],1));
            x=fa[x];
        }
        return mx+A[a];
    }
}S;
void insert(char *str,int p){
    int x=0;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        int &pos=son[x][str[i]-'a'];
        if(!pos)pos=++tot;
        x=pos;
    }
    to[p]=x;
}
void Getnxt(){
    queue<int>q;
    for(int i=0;i<26;i++)
        if(son[0][i]){
            q.push(son[0][i]);
            fa[son[0][i]]=0;
            G.add_edge(0,son[0][i]);
        }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
            if(son[x][i]){
                nxt[son[x][i]]=son[nxt[x]][i];
                fa[son[x][i]]=x;
                G.add_edge(nxt[son[x][i]],son[x][i]);
                q.push(son[x][i]);
            }else son[x][i]=son[nxt[x]][i];
    }
}
void clear(){
    for(int i=0;i<=tot;i++){
        nxt[i]=0;
        memset(son[i],0,sizeof(son[i]));
        G.head[i]=0;
    }   
    G.id=tot=0;
}
bool cur2;
int main(){
//  double sz=&cur2-&cur1;
//  cout<<sz/1024<<endl;
    for(int _,cas=(cin>>_,1);cas<=_;cas++){
        clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%s%d",str,&A[i]);
            insert(str,i);
        }
        Getnxt();
        S.Build();
        int ans=0;
        for(int i=1;i<=n;i++){
            A[i]=S.solve(i);
            ans=max(ans,A[i]);
            S.add(i);
        }
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0.0;
}

专题P

题解写在203上。