后缀自动机SAM

luckydrawbox · 2024-02-08 22:03:05 · 个人记录

变量

函数

代码

struct SAM{
    int tot,lst;
    struct Node{
        int len,fa,ch[26];
        Node(){memset(ch,0,sizeof(ch));len=fa=0;}
    }a[N<<1];
    SAM(){tot=lst=1;}
    void insert(int c){
        int p=lst,np=lst=++tot,q,nq;
        a[np].len=a[p].len+1;
        for(;p&&!a[p].ch[c];p=a[p].fa)a[p].ch[c]=np;
        if(!p)a[np].fa=1;
        else{
            q=a[p].ch[c];
            if(a[q].len==a[p].len+1)a[np].fa=q;
            else{
                nq=++tot;a[nq]=a[q];
                a[nq].len=a[p].len+1;a[q].fa=a[np].fa=nq;
                for(;p&&a[p].ch[c]==q;p=a[p].fa)a[p].ch[c]=nq;
            }
        }
    }
}sam;