代码

#define BENCH_N 1000000
#define BENCH_SEED 202609220061ULL
// 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 std::string all_output; static char obuf[1<<20];static size_t opos;
static void flush(){all_output.append(obuf,opos);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;}
struct RNG {
 uint64_t state;
 uint64_t next(){ uint64_t z=(state+=0x9e3779b97f4a7c15ULL);z=(z^(z>>30))*0xbf58476d1ce4e5b9ULL;z=(z^(z>>27))*0x94d049bb133111ebULL;return z^(z>>31); }
 uint32_t uniform(uint32_t bound){uint32_t x,threshold=-bound%bound; do{x=uint32_t(next());}while(x<threshold); return x%bound;}
};

int main(){
 std::string s(BENCH_N,' ' ); RNG rng{BENCH_SEED}; for(char &c:s)c=char('a'+rng.uniform(26)); all_output.reserve(BENCH_N*11ULL);
 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(); uint64_t hash=1469598103934665603ULL; for(unsigned char c:all_output){hash^=c;hash*=1099511628211ULL;} printf("n=%zu bytes=%zu hash=%llu\n",n,all_output.size(),(unsigned long long)hash);
}

评测结果