后缀数组

lhm_ · 2019-12-08 14:24:00 · 个人记录

将字符串每个后缀按照字典序排序

$rk:$表示起始位置为$i$的后缀的排名 $sa[rk[i]]=i,\ rk[sa[i]]=i

通过倍增和基数排序来实现O(n\ log\ n)的排序

基数排序时先排第一关键字，再在第一关键字相同下排第二关键字

第二关键字本身是有序的

$tp:$表示排名为$num$的后缀的位置，也是第二关键字排名为$i$的后缀的起始位置 $rk[tp[i]]$即为排名为$i$的第二关键字对应的第一关键字 $b[rk[tp[i]]]$即为当第一关键字相同时，第二关键字较大的该后缀的排名所以$sa[b[rk[tp[i]]]--]=tp[i]

$LCP$最长公共前缀 $ht:$表示$suff(sa[i])$和$suff(sa[i-1])$的最长公共前缀 $h:$表示$ht[rk[i]]$，$suff(i)$和排序后它前一位的后缀的最长公共前缀 ![](https://s2.ax1x.com/2019/12/09/QdbrIf.png) $h[i] \geqslant h[i-1]-1

所以suff(i)和它前一位后缀的最长公共前缀至少为h[i-1]-1

本质不同的子串个数：\sum\limits_{i=1}^n n-sa_i+1-ht_i=\frac{n(n+1)}{2}-\sum\limits_{i=1}^n ht_i

code:

void rsort()
{
    for(int i=0;i<=m;++i) b[i]=0;
    for(int i=1;i<=n;++i) b[rk[i]]++;
    for(int i=1;i<=m;++i) b[i]+=b[i-1];
    for(int i=n;i;--i) sa[b[rk[tp[i]]]--]=tp[i];
}
void SA()
{
    for(int i=1;i<=n;++i) rk[i]=s[i],tp[i]=i;
    rsort();
    for(int k=1;k<=n;k<<=1)
    {
        int num=0;
        for(int i=n-k+1;i<=n;++i) tp[++num]=i;
        for(int i=1;i<=n;++i) 
            if(sa[i]>k)
                tp[++num]=sa[i]-k;
        rsort();
        memcpy(tp,rk,sizeof(rk));
        rk[sa[1]]=num=1;
        for(int i=2;i<=n;++i)
            rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?num:++num;
        if(num==n) break;
        m=num;
    }
}
void height()
{
    int k=0;
    for(int i=1;i<=n;++i) rk[sa[i]]=i;
    for(int i=1;i<=n;++i)
    {
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k]) k++;
        ht[rk[i]]=k;
    }
}

两个后缀的LCP为区间height数组的最小值

code:

void ST()
{
    lg[0]=-1;
    for(int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;++i) f[i][0]=ht[i];
    for(int j=1;j<=20;++j)
        for(int i=1;i+(1<<j)-1<=n;++i)
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int lcp(int l,int r)
{
    l=rk[l],r=rk[r];
    if(l>r) swap(l,r);
    l++;
    int len=lg[r-l+1];
    return min(f[l][len],f[r-(1<<len)+1][len]);
}