代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    char buf[100010];
    if (!fgets(buf, sizeof(buf), stdin)) return 0;
    string s(buf);
    while (!s.empty() && (s.back()=='\n'||s.back()=='\r')) s.pop_back();
    int n = s.size();
    vector<int> sa(n), rnk(n), tmp(n);
    for (int i=0;i<n;i++){sa[i]=i;rnk[i]=s[i];}
    for (int k=1;k<n;k*=2){
        auto cmp=[&](int x,int y){
            if(rnk[x]!=rnk[y])return rnk[x]<rnk[y];
            int rx=x+k<n?rnk[x+k]:-1;
            int ry=y+k<n?rnk[y+k]:-1;
            return rx<ry;
        };
        sort(sa.begin(),sa.end(),cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<n;i++)tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
        swap(tmp,rnk);
    }
    vector<int> r(n);
    for(int i=0;i<n;i++)r[sa[i]]=i;
    vector<int> h(n,0);
    int k=0;
    for(int i=0;i<n;i++){
        if(r[i]==0){k=0;continue;}
        if(k)k--;
        int j=sa[r[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        h[r[i]]=k;
    }
    for(int i=0;i<n;i++)printf("%d%c",sa[i]+1,i==n-1?'\n':' ');
    for(int i=1;i<n;i++)printf("%d%c",h[i],i==n-1?'\n':' ');
    if(n==1)printf("\n");
    return 0;
}

评测结果