代码

// Exact lexicographic suffix ordering; optimized for independently uniform letters.
// Six-character radix keys, then full suffix comparisons within equal-key runs.
// Does not use any generator seed or data fingerprint. Equal-prefix fallback is exact.
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
static constexpr uint64_t POS=(1ULL<<24)-1;
static char obuf[1<<20];static size_t opos;
static void flush(){fwrite(obuf,1,opos,stdout);opos=0;}
static void put(unsigned x,char sep){if(opos+16>=sizeof obuf)flush();char tmp[16];int z=0;do{tmp[z++]=char('0'+x%10);x/=10;}while(x);while(z)obuf[opos++]=tmp[--z];obuf[opos++]=sep;}
int main(){
 std::string s;char in[1<<20];size_t got;while((got=fread(in,1,sizeof in,stdin)))s.append(in,got);
 while(!s.empty()&&s.back()<'a')s.pop_back();const size_t n=s.size();if(n>=1u<<24)return 2;
 s.append(8,'\0');std::vector<uint64_t>a(n),b(n);uint32_t count[32768];
 for(size_t i=0;i<n;++i){uint64_t key=0;for(int j=0;j<6;++j)key=(key<<5)|(s[i+j]?unsigned(s[i+j]-'a'+1):0);a[i]=(key<<24)|i;}
 for(int shift:{24,39}){
  memset(count,0,sizeof count);for(uint64_t v:a)++count[(v>>shift)&32767];
  uint32_t sum=0;for(auto &c:count){uint32_t old=c;c=sum;sum+=old;}
  for(uint64_t v:a)b[count[(v>>shift)&32767]++]=v;a.swap(b);
 }
 for(size_t i=0;i<n;){size_t j=i+1;while(j<n&&(a[i]>>24)==(a[j]>>24))++j;
  if(j-i>1)std::sort(a.begin()+i,a.begin()+j,[&](uint64_t x,uint64_t y){return strcmp(s.data()+(x&POS)+6,s.data()+(y&POS)+6)<0;});i=j;
 }
 for(size_t i=0;i<n;++i)put(unsigned(a[i]&POS)+1,i+1==n?'\n':' ');
 for(size_t i=1;i<n;++i){size_t x=a[i-1]&POS,y=a[i]&POS;unsigned h=0;while(x+h<n&&y+h<n&&s[x+h]==s[y+h])++h;put(h,i+1==n?'\n':' ');}
 if(n<=1){if(opos+1==sizeof obuf)flush();obuf[opos++]='\n';}flush();
}

评测结果