后缀树

luckydrawbox · 2024-02-22 20:06:02 · 算法·理论

变量

函数

代码

struct SufTree{
    int tot,tpos,now,rem,inf;
    int s[N];
    struct Node{
        int link,st,len,ch[27];
    }a[N<<1];
    SufTree(){
        tot=now=1,tpos=rem=0;
        a[0].len=inf=1e9;
    }
    int make(int st,int len){
        a[++tot].link=1;a[tot].st=st;
        a[tot].len=len;return tot;
    }
    void extend(int x){
        s[++tpos]=x;rem++;
        for(int lst=1;rem;){
            while(rem>a[a[now].ch[s[tpos-rem+1]]].len)
                rem-=a[now=a[now].ch[s[tpos-rem+1]]].len;
            int p=a[now].ch[s[tpos-rem+1]],q;
            int c=s[a[p].st+rem-1];
            if(!p||x==c){
                a[lst].link=now;lst=now;
                if(!p)a[now].ch[s[tpos-rem+1]]=make(tpos,inf);
                else break;
            }
            else{
                q=make(a[p].st,rem-1);
                a[q].ch[c]=p;
                a[q].ch[x]=make(tpos,inf);
                a[p].st+=rem-1;a[p].len-=rem-1;
                a[lst].link=a[now].ch[s[tpos-rem+1]]=q;
                lst=q;
            }
            if(now==1)rem--;else now=a[now].link;
        }
    }
}st;