OI-Wiki

Record

把临时数组改成了自己写的 struct 滚动数组，所以变成了下标 0 表示上一个版本的数组，下标 1 表示当前修改的数组，其他的部分就是按照 OI-Wiki 上的写法实现的。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
#define mp make_pair

inline int read(){
    int ret=0;
    char ch=' ',c=getchar();
    while(!('0'<=c&&c<='9')) ch=c,c=getchar();
    while('0'<=c&&c<='9') ret=ret*10+(c^48),c=getchar();
    return ch=='-'?-ret:ret;
}

const int N=1e6+10;
class roll_arr{
private:
    int a[2][N<<1];
    int sz;
    int last,now;
public:
    roll_arr(int x=0){
        last=0,now=1;
        sz=x;
        memset(a[0]+1,0,sz*sizeof(int));
        memset(a[1]+1,0,sz*sizeof(int));
    }
    void roll(){ last=now,now^=1; }
    int* operator[] (const int x){
        if(x==0) return a[last];
        else return a[now];
    }
};

int n;
char s[N];
int buk[N];
roll_arr sa(N-10),rk((N-10)<<1);

void solve(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) buk[rk[1][i]=s[i]]++;
    for(int i=1;i<=127;i++) buk[i]+=buk[i-1];
    for(int i=n;i>=1;i--) sa[1][buk[rk[1][i]]--]=i;
    rk.roll();
    for(int now=0,i=1;i<=n;i++){
        if(rk[0][sa[1][i-1]]!=rk[0][sa[1][i]]) now++;
        rk[1][sa[1][i]]=now;
    }
    for(int w=1;w<n;w<<=1){
        memset(buk+1,0,n*sizeof(int));
        sa.roll();
        for(int i=1;i<=n;i++) buk[rk[1][sa[0][i]+w]]++;
        for(int i=1;i<=n;i++) buk[i]+=buk[i-1];
        for(int i=n;i>=1;i--) sa[1][buk[rk[1][sa[0][i]+w]]--]=sa[0][i];
        memset(buk+1,0,n*sizeof(int));
        sa.roll();
        for(int i=1;i<=n;i++) buk[rk[1][sa[0][i]]]++;
        for(int i=1;i<=n;i++) buk[i]+=buk[i-1];
        for(int i=n;i>=1;i--) sa[1][buk[rk[1][sa[0][i]]]--]=sa[0][i];
        rk.roll();
        for(int now=0,i=1;i<=n;i++){
            if(rk[0][sa[1][i-1]]!=rk[0][sa[1][i-1]]||rk[0][sa[1][i-1]+w]!=rk[0][sa[1][i]+w]) now++;
            rk[1][sa[1][i]]=now;
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",sa[1][i]);
}

int main(){
    solve();
    return 0;
}