后缀全家桶

donotctjuntilAFO · 2023-03-14 17:16:00 · 算法·理论

前言

后缀全家桶应用还挺多的。

正文

后缀数组

概念

后缀 i 表示 s[i...n]

性质：height_{rk_i}\ge height_{rk_{i-1}}-1

本质不同的子串数目

为 \dfrac{n(n+1)}{2}-\displaystyle \sum_{i=2}^{n}height_i

后缀自动机

概念介绍

后缀自动机就是将一个能表示所有子串的 DAG 和一棵表示不同的 Endpos 的树（叫 Parent 树）共用点集的一个东西。

记录一下东西：

构造方法

增量法。

已知 |S| 的 SAM ,构造 |S|+c 的 SAM 。

先新建一个节点 np ，设当前结尾为 p,q=trie_{p,c} 。

如果 |S| 中没有出现 c ，那么就从 |S| 代表的节点一直跳 fa ，每经过一个节点就连一条 c 的边，之后 fa_{np}=0。

否则如果 len_p+1=len_q ，令 fa_{np}=q 即可。

否则 分裂 q ，设分裂出来的节点为 nq ，先将 q 的所有信息继承到 nq ，然后令 fa_{np}=nq,fa_q=nq,len_{nq}=len_p+1 , 最后将 p 在 Parent 树上的所有祖先中原本指向 q 的点连向 nq 。

原理：没有 c ，连 c 显然。

广义后缀自动机

就是在 trie 树上跑 SAM ，支持处理多个串。

在线做法是将 lst=1 ，然后加两个特判。

代码：

int extand(int c){
    if(trie[lst][c]&&len[trie[lst][c]]==len[lst]+1)
        return trie[lst][c];
    int p=lst,q,now;bool ok=0;
    for(len[now=++cnt]=len[p]+1;p&&!trie[p][c];p=fa[p])
        trie[p][c]=now;
    if(!p){fa[now]=1;return now;}
    if(len[q=trie[p][c]]==len[p]+1){fa[now]=q;return now;}
    if(p==lst) ok=1,now=0,--cnt;
    len[++cnt]=len[p]+1;
    f(i,0,25)
        trie[cnt][i]=trie[q][i];
    fa[cnt]=fa[q],fa[q]=fa[now]=cnt;
    for(int i=p;trie[i][c]==q;i=fa[i])
        trie[i][c]=cnt;
    return ok?cnt:now;
}

后缀平衡树

我们将后缀排名插入平衡树即可得到后缀平衡树，特别地，后缀平衡树的中序遍历就是后缀数组。

如果这么理解就和后缀数组没啥区别了。

主要看如何在线构造，后缀平衡树支持在前端插入或删除字符。每次插入时，根据已有的后缀信息比较，每个后缀赋个权值即可，当不平衡时，暴力重赋权值。

代码：

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define F(i,r,l) for(int i=r;i>=l;--i)
#define LL long long
#define ULL unsigned long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define read(n) {int _x=0,_ty=1;char _c=getchar();while(!isdigit(_c)){if(_c=='-')_ty=-1;_c=getchar();}while(isdigit(_c))_x=10*_x+_c-'0',_c=getchar();n=_x*_ty;}
char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
const int N=800005;
const LL INF=1e18;
int n,rt,mask,ans;
char a[N],t[N];
struct node{
    int son[2],siz,rnd;
    LL val;
}tree[N];
inline void decode(char *ch,int mask){
    int l=strlen(ch);
    for(int i=0;i<l;i++){
        mask=(mask*131+i)%l;
        char t=ch[i];
        ch[i]=ch[mask];
        ch[mask]=t;
    }
}
inline int cmp(int x,int y){
    if(a[x]>a[y]||a[x]==a[y]&&tree[x-1].val>tree[y-1].val) return 1;
    if(a[x]==a[y]&&tree[x-1].val==tree[y-1].val) return 0;
    return -1;
}
inline bool check(int x){for(int i=1,j=x;t[i];++i,--j){if(t[i]<a[j])return 1;if(t[i]>a[j])return 0;}}
inline void pushup(int x){tree[x].siz=tree[tree[x].son[0]].siz+tree[tree[x].son[1]].siz+1;}
inline void rebuild(int x,LL l,LL r){
    tree[x].val=l+r>>1;
    if(tree[x].son[0]) rebuild(tree[x].son[0],l,tree[x].val-1);
    if(tree[x].son[1]) rebuild(tree[x].son[1],tree[x].val+1,r);
}
inline void rotate(int &x,bool op,LL l,LL r){
    int s=tree[x].son[op^1];
    tree[x].son[op^1]=tree[s].son[op];
    tree[s].son[op]=x;
    pushup(x),pushup(s),x=s;
    rebuild(x,l,r);
}
inline void insert(int v,int &x,LL l,LL r){
    if(!x){tree[x=v]=(node){{0,0},1,rand(),l+r>>1};return ;}
    bool ok=cmp(x,v)<0;
    insert(v,tree[x].son[ok],ok?tree[x].val+1:l,ok?r:tree[x].val-1);
    pushup(x);
    if(tree[x].rnd>tree[tree[x].son[ok]].rnd) rotate(x,ok^1,l,r);
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tree[x].rnd>tree[y].rnd) return tree[y].son[0]=merge(x,tree[y].son[0]),pushup(y),y;
    else return tree[x].son[1]=merge(tree[x].son[1],y),pushup(x),x;
}
inline void erase(int v,int &x,LL l,LL r){
    if(!x) return ;
    int ok=cmp(x,v);
    if(!ok){x=merge(tree[x].son[0],tree[x].son[1]);if(x)rebuild(x,l,r);}
    else erase(v,tree[x].son[ok<0],ok<0?tree[x].val+1:l,ok<0?r:tree[x].val-1);
    if(x) pushup(x);
}
inline int rnk(int x){
    if(!x) return 1;
    if(check(x)) return rnk(tree[x].son[0]);
    else return tree[tree[x].son[0]].siz+1+rnk(tree[x].son[1]);
}
int main(){
    srand(time(0));
    read(n);
    int len=0;
    char c=getchar();
    while(c<'A'||c>'Z') c=getchar();
    while('A'<=c&&c<='Z') a[++len]=c,c=getchar();
    a[len+1]=0;
    f(i,1,len)
        insert(i,rt,1,INF);
    while(n--){
        int x;
        char op,c=getchar();
        while(c<'A'||c>'Z') c=getchar();
        while('A'<=c&&c<='Z') op=c,c=getchar();
        if(op=='D'){
            int l=0;
            char c=getchar();
            while(c<'A'||c>'Z') c=getchar();
            while('A'<=c&&c<='Z') t[++l]=c,c=getchar();
            t[l+1]=0;
            decode(t+1,mask);
            f(i,len+1,len+l)
                a[i]=t[i-len],insert(i,rt,1,INF);
            len+=l;
        }
        else if(op=='L'){
            read(x);
            F(i,len,len-x+1)
                erase(i,rt,1,INF);
            len-=x;
        }
        else{
            int l=0;
            char c=getchar();
            while(c<'A'||c>'Z') c=getchar();
            while('A'<=c&&c<='Z') t[++l]=c,c=getchar();
            t[l+1]=0;
            decode(t+1,mask);
            reverse(t+1,t+l+1);
            t[l+1]='Z'+1,t[l+2]=0;
            ans=rnk(rt);--t[l];
            ans-=rnk(rt);
            mask^=ans;
            printf("%d\n",ans);
        }
    }
    return 0;
}

后缀树

将 S 的所有后缀插入 trie 中就得到了后缀 Trie，后缀 Trie 可以表示 S 的所有子串。但暴力为 O(n^2) ,考虑压缩。令后缀 trie 中所有拥有多于一个儿子的节点和后缀节点为关键点。只保留关键点，将非关键点形成的链压缩成一条边形成的压缩 trie 树就为为后缀树。复杂度 O(n) 。

建法：反串跑SAM的Parent树即为后缀树。