后缀数组SA

· · 个人记录

变量

函数

代码

struct SA{
    int k1[N],k2[N],c[N],sa[N],rk[N],h[N];
    void qsa(int n,int m,string s){
        for(int i=1;i<=n;i++)c[k1[i]=s[i]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=1;i<=n;i++)sa[c[k1[i]]--]=i;
        for(int b=1,tot;b<=n;b<<=1){
            tot=0;
            for(int i=n-b+1;i<=n;i++)k2[++tot]=i;
            for(int i=1;i<=n;i++)
                if(sa[i]>b)k2[++tot]=sa[i]-b;
            for(int i=1;i<=m;i++)c[i]=0;
            for(int i=1;i<=n;i++)c[k1[i]]++;
            for(int i=1;i<=m;i++)c[i]+=c[i-1];
            for(int i=n;i>=1;i--)
                sa[c[k1[k2[i]]]--]=k2[i],k2[i]=0;
            swap(k1,k2);tot=1;k1[sa[1]]=1;
            for(int i=2;i<=n;i++)
                if(k2[sa[i]]==k2[sa[i-1]]&&k2[sa[i]+b]==k2[sa[i-1]+b])
                    k1[sa[i]]=tot;
                else k1[sa[i]]=++tot;
            if(tot==n)break;
            m=tot;
        }
        for(int i=1;i<=n;i++)rk[sa[i]]=i;
        for(int i=1,k=0;i<=n;i++){
            if(k)k--;
            while(s[i+k]==s[sa[rk[i]-1]+k])k++;
            h[rk[i]]=k;
        }
    }
}st;