题目概述

Suffix Sort

解题报告

一直在想Hash，然后寄了……

实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表示 $S_i$ 与上一个相同字符的距离（如果不存在则为 $i$ ），然后当比较后缀 $i$ 和后缀 $j$ 时，把 $a_i$ 到 $a_n$ 中 $k-a_k<i$ 的那些位置改成 $0$ ，后缀 $j$ 同理，然后就可以直接比较 $a_{[i,n]}$ 和 $a_{[j,n]}$ 了。

由于只有小写字符，因此最多只有 $26$ 个位置需要改成 $0$ ，所以如果把后缀 $i$ 和后缀 $j$ 结合起来考虑，会把 $a$ 分为 $52$ 个段，对于段的分割节点，我们特殊判断，而分割节点中间的连续段我们可以直接利用 $LCP$ 判断是否全相同。

这样每次比较的复杂度就是 $O(26)$ 了，直接sort就可以得到排名，复杂度 $O(26n\log_2n)$ 。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=200000,maxi=26,LOG=17;

int n,a[maxn+5],lst[maxi],ID[maxn+5];char s[maxn+5];
int SA[maxn+5],rk[maxn+5],ha[maxn+5],sc[(maxn<<1)+5];
int lg[maxn+5],RMQ[LOG+1][maxn+5];
int nxt[maxi][maxn+5],cnt[maxn+5];
pair<int,int> pos[maxn+5][maxi+5];
int who[maxn+5][maxi];

void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[sc[i]]]--]=sc[i];
}
void MakeSA(int *s,int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],sc[i]=i,sc[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) sc[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) sc[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) sc[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++)
            rk[SA[i]]=(p+=sc[SA[i-1]]!=sc[SA[i]] || sc[SA[i-1]+k]!=sc[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++){
        if (k) k--;
        while (s[i+k]==s[SA[rk[i]-1]+k]) k++;
        RMQ[0][rk[i]]=k;
    }
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int j=1;(1<<j)<n;j++)
        for (int i=2;i+(1<<j)-1<=n;i++)
            RMQ[j][i]=min(RMQ[j-1][i],RMQ[j-1][i+(1<<j-1)]);
}
int LCP(int x,int y){
    if (x>y) swap(x,y);x++;
    int k=lg[y-x+1];
    return min(RMQ[k][x],RMQ[k][y-(1<<k)+1]);
}
bool cmp(const int &x,const int &y){
    if (x==y) return false;
    for (int i=1;i<=cnt[x] && i<=cnt[y];i++){
        if (pos[x][i].fr==n || pos[y][i].fr==n) return x>y;
        int Lx=pos[x][i].fr+1,Rx=(i<cnt[x]?pos[x][i+1].fr-1:n),lenx=Rx-Lx+1;
        int Ly=pos[y][i].fr+1,Ry=(i<cnt[y]?pos[y][i+1].fr-1:n),leny=Ry-Ly+1;
        int lcp=LCP(rk[Lx],rk[Ly]);
        if (lcp<lenx && lcp<leny) return who[x][s[Lx+lcp]-'a']<who[y][s[Ly+lcp]-'a'];
        if (Rx==n || Ry==n) return x>y;
        if (lenx!=leny) return lenx>leny;
    }
    return x>y;
}
struct fastO{
    int si;char buf[1<<16];
    fastO() {si=0;}
    void putc(char ch){
        if (si==(1<<16)) fwrite(buf,1,si,stdout),si=0;
        buf[si++]=ch;
    }
    ~fastO() {fwrite(buf,1,si,stdout);}
}fo;
template<typename T> void writei(T x,char ch='\n'){
    int len=0,buf[100];
    if (x<0) fo.putc('-'),x=-x;
    do buf[len++]=x%10,x/=10; while (x);
    while (len) fo.putc(buf[--len]+48);
    fo.putc(ch);
}
int main(){
    scanf("%d%s",&n,s+1);
    for (int i=1;i<=n;i++) a[i]=i-lst[s[i]-'a'],lst[s[i]-'a']=i;
    MakeSA(a,n,n);
    for (int j=0;j<maxi;j++) lst[j]=n+1;
    for (int i=n;i;i--){
        lst[s[i]-'a']=i;
        for (int j=0;j<maxi;j++) nxt[j][i]=lst[j];
        cnt[i]=0;
        for (int j=0;j<maxi;j++) if (nxt[j][i]<=n) pos[i][++cnt[i]]=mp(nxt[j][i],j);
        sort(pos[i]+1,pos[i]+1+cnt[i]);
        for (int j=1;j<=cnt[i];j++) who[i][pos[i][j].sc]=j;
    }
    for (int i=1;i<=n;i++) ID[i]=i;
    sort(ID+1,ID+1+n,cmp);
    for (int i=1;i<=n;i++) writei(ID[i],i<n?' ':'\n');
    return 0;
}