代码

#define JUDGE 1
// 1006e6 v2: suffix array + LCP for a uniformly-random lowercase string.
//   stage 1  MSD by the first KC chars (KC=1 -> 27 buckets, KC=2 -> 729)
//   stage 2  per bucket, LSD radix by the remaining chars (DC chars per digit), in L1/L2
//   stage 3  one pass: refine equal-6-char-key runs by insertion sort + compute LCP by
//            48-bit key compare (8-byte load, clz)
//   stage 4  fast digit output
// Fallback to SA-IS when the data is not random (oversized bucket / too-long run).
#include <cstdint>
#include <cstring>

#define MAXN 1000005
#define PADB 32

static unsigned char str[MAXN + PADB];
static uint32_t AA[MAXN], BB[MAXN];
static uint32_t CNT[1 << 12];
static uint32_t gstart[1 << 12];
#define TMPSZ (1 << 16)
static uint32_t TMP[TMPSZ];
static int sa_[MAXN];
static int lcp_[MAXN];
static unsigned char gmap[256];
static inline unsigned long long rd() { return __builtin_ia32_rdtsc(); }
static unsigned long long P2[16];

#ifndef KC
#define KC 2          /* chars used for the MSD digit */
#endif
#ifndef DC
#define DC 2          /* chars per digit inside a bucket */
#endif

#define OUTMAX (12u << 20)
static char OUT[OUTMAX];

static void build_map() {
  for (int i = 0; i < 256; i++) gmap[i] = 0;
  for (int c = 'a'; c <= 'z'; c++) gmap[c] = (unsigned char)(c - 'a' + 1);
}

static inline uint32_t d1(const unsigned char *p) { return gmap[p[0]]; }
// order-preserving big-endian packing of two chars (pad=0 < 'a'..'z' = 1..26)
static inline uint32_t d2(const unsigned char *p) {
  return ((uint32_t)gmap[p[0]] << 5) | (uint32_t)gmap[p[1]];
}

// ---------- stage 1 ----------
// returns the number of buckets; fills gstart[]
static uint32_t msd_stage(const unsigned char *s, uint32_t *dst, int n) {
  const uint32_t nb = (KC == 1) ? 27 : 859;
  memset(CNT, 0, sizeof(uint32_t) * nb);
  if (KC == 1) { for (int i = 0; i < n; i++) CNT[d1(s + i)]++; }
  else { for (int i = 0; i < n; i++) CNT[d2(s + i)]++; }
  uint32_t sum = 0;
  for (uint32_t d = 0; d < nb; d++) { uint32_t c = CNT[d]; gstart[d] = sum; CNT[d] = sum; sum += c; }
  gstart[nb] = sum;
  if (KC == 1) { for (int i = 0; i < n; i++) dst[CNT[d1(s + i)]++] = (uint32_t)i; }
  else { for (int i = 0; i < n; i++) dst[CNT[d2(s + i)]++] = (uint32_t)i; }
  return nb;
}

// ---------- stage 2: LSD the bucket [lo,hi) of AA by chars KC..5 ----------
// digit table: bases[]/widths[] from the least significant end
static int g_nd;
static int g_base[8], g_nb[8];

static void plan_digits() {
  int end = 6, nd = 0;
  while (end > KC) {
    int b = end - DC; if (b < KC) b = KC;
    int w = end - b;
    g_base[nd] = b;
    g_nb[nd] = (w == 1) ? 27 : 859;
    nd++; end = b;
  }
  g_nd = nd;
}

static inline uint32_t digit_at(const unsigned char *s, uint32_t idx, int p) {
  const unsigned char *q = s + idx + g_base[p];
  if (g_nb[p] == 27) return d1(q);
  return d2(q);
}

static int bucket_sort_lsd(const unsigned char *s, uint32_t lo, uint32_t hi) {
  uint32_t m = hi - lo;
  if (m <= 1) return 0;
  if (m > TMPSZ) return -1;
  uint32_t *cur = AA + lo;
  for (int p = 0; p < g_nd; p++) {
    uint32_t nb = (uint32_t)g_nb[p];
    uint32_t *nx = ((p & 1) == 0) ? TMP : (AA + lo);
    memset(CNT, 0, sizeof(uint32_t) * nb);
    for (uint32_t i = 0; i < m; i++) CNT[digit_at(s, cur[i], p)]++;
    uint32_t sum = 0;
    for (uint32_t d = 0; d < nb; d++) { uint32_t c = CNT[d]; CNT[d] = sum; sum += c; }
    for (uint32_t i = 0; i < m; i++) { uint32_t v = cur[i]; nx[CNT[digit_at(s, v, p)]++] = v; }
    cur = nx;
  }
  if ((g_nd & 1) != 0) memcpy(AA + lo, TMP, m * 4);   // odd #passes leaves the result in TMP
  return 0;
}

// ---------- fast output ----------
static const char DIG2[201] =
  "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
  "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
  "8081828384858687888990919293949596979899";
// 4-digit table: DIG4[i] = the 4 ASCII chars of i (zero padded), little-endian u32
static uint32_t DIG4[10000];
static void build_dig4() {
  for (int i = 0; i < 10000; i++) {
    char t[4];
    t[0] = (char)('0' + i / 1000); t[1] = (char)('0' + (i / 100) % 10);
    t[2] = (char)('0' + (i / 10) % 10); t[3] = (char)('0' + i % 10);
    memcpy(&DIG4[i], t, 4);
  }
}
// writes 8 bytes (may overrun by up to 7) and advances by the exact digit count
static inline char *putu(char *p, unsigned v) {
  uint32_t hi = v / 10000, lo = v % 10000;
  uint64_t u = (uint64_t)DIG4[hi] | ((uint64_t)DIG4[lo] << 32);
  int len = 1 + (v >= 10) + (v >= 100) + (v >= 1000) + (v >= 10000)
              + (v >= 100000) + (v >= 1000000) + (v >= 10000000);
  u >>= (8 - len) * 8;            // move the left zero padding to the tail
  memcpy(p, &u, 8);
  return p + len;
}
// byte-exact writer for the final element of each line
static inline char *putu_exact(char *p, unsigned v) {
  char tmp[8];
  int i = 8;
  while (v >= 100) {
    unsigned q = v / 100, r = v - q * 100;
    tmp[--i] = DIG2[r * 2 + 1]; tmp[--i] = DIG2[r * 2];
    v = q;
  }
  if (v >= 10) { tmp[--i] = DIG2[v * 2 + 1]; tmp[--i] = DIG2[v * 2]; }
  else tmp[--i] = (char)('0' + v);
  int len = 8 - i;
  memcpy(p, tmp + i, len);
  return p + len;
}

// ---------- SA-IS fallback ----------
#define TPOOL 24
static int g_bkt[MAXN + 2];
static int g_cntc[MAXN + 2];
static unsigned char t_pool[TPOOL][(MAXN + 7) / 8];
static inline int tget(const unsigned char *t, int i) { return (t[i >> 3] >> (i & 7)) & 1; }
static inline void tset(unsigned char *t, int i, int b) {
  if (b) t[i >> 3] |= (unsigned char)(1 << (i & 7));
  else t[i >> 3] &= (unsigned char)~(1 << (i & 7));
}
static inline int isLMS(const unsigned char *t, int i) { return i > 0 && tget(t, i) && !tget(t, i - 1); }
template <typename T> static void getCounts(const T *s, int *C, int n, int K) {
  for (int i = 0; i <= K; i++) C[i] = 0;
  for (int i = 0; i < n; i++) C[(int)s[i]]++;
}
static void getBuckets(const int *C, int *B, int K, bool end) {
  int sum = 0;
  if (end) { for (int i = 0; i <= K; i++) { sum += C[i]; B[i] = sum; } }
  else { for (int i = 0; i <= K; i++) { B[i] = sum; sum += C[i]; } }
}
template <typename T> static void induceSAl(const unsigned char *t, int *SA, const T *s, int *bkt, int n, int K) {
  getBuckets(g_cntc, bkt, K, false);
  for (int i = 0; i < n; i++) { int j = SA[i] - 1; if (j >= 0 && !tget(t, j)) SA[bkt[(int)s[j]]++] = j; }
}
template <typename T> static void induceSAs(const unsigned char *t, int *SA, const T *s, int *bkt, int n, int K) {
  getBuckets(g_cntc, bkt, K, true);
  for (int i = n - 1; i >= 0; i--) { int j = SA[i] - 1; if (j >= 0 && tget(t, j)) SA[--bkt[(int)s[j]]] = j; }
}
template <typename T> static void sais(const T *s, int *SA, int n, int K, int depth) {
  unsigned char *t = t_pool[depth];
  int *bkt = g_bkt;
  int i, j;
  tset(t, n - 2, 0); tset(t, n - 1, 1);
  for (i = n - 3; i >= 0; i--) tset(t, i, (s[i] < s[i + 1] || (s[i] == s[i + 1] && tget(t, i + 1))));
  getCounts(s, g_cntc, n, K);
  getBuckets(g_cntc, bkt, K, true);
  for (i = 0; i < n; i++) SA[i] = -1;
  for (i = 1; i < n; i++) if (isLMS(t, i)) SA[--bkt[(int)s[i]]] = i;
  induceSAl(t, SA, s, bkt, n, K);
  induceSAs(t, SA, s, bkt, n, K);
  int n1 = 0;
  for (i = 0; i < n; i++) if (isLMS(t, SA[i])) SA[n1++] = SA[i];
  for (i = n1; i < n; i++) SA[i] = -1;
  int name = 0, prev = -1;
  for (i = 0; i < n1; i++) {
    int pos = SA[i];
    bool diff = false;
    int dmax = n - (pos > prev ? pos : prev);
    for (int d = 0; d < dmax; d++)
      if (prev == -1 || s[pos + d] != s[prev + d] || tget(t, pos + d) != tget(t, prev + d)) { diff = true; break; }
      else if (d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d))) break;
    if (diff) { name++; prev = pos; }
    pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
    SA[n1 + pos] = name - 1;
  }
  for (i = n - 1, j = n - 1; i >= n1; i--) if (SA[i] >= 0) SA[j--] = SA[i];
  int *SA1 = SA, *s1 = SA + n - n1;
  if (name < n1) sais<int>(s1, SA1, n1, name - 1, depth + 1);
  else for (i = 0; i < n1; i++) SA1[s1[i]] = i;
  getCounts(s, g_cntc, n, K);
  getBuckets(g_cntc, bkt, K, true);
  for (i = 1, j = 0; i < n; i++) if (isLMS(t, i)) s1[j++] = i;
  for (i = 0; i < n1; i++) SA1[i] = s1[SA1[i]];
  for (i = n1; i < n; i++) SA[i] = -1;
  for (i = n1 - 1; i >= 0; i--) { j = SA[i]; SA[i] = -1; SA[--bkt[(int)s[j]]] = j; }
  induceSAl(t, SA, s, bkt, n, K);
  induceSAs(t, SA, s, bkt, n, K);
}

// ---------- helpers ----------
static inline uint64_t key48(const unsigned char *p) {
  uint64_t x; memcpy(&x, p, 8); return __builtin_bswap64(x) >> 16;
}
static inline bool suf_less(const unsigned char *s, uint32_t i, uint32_t j) {
  const unsigned char *p = s + i, *q = s + j;
  for (;;) {
    uint64_t a; memcpy(&a, p, 8); a = __builtin_bswap64(a);
    uint64_t b; memcpy(&b, q, 8); b = __builtin_bswap64(b);
    if (a != b) return a < b;
    p += 8; q += 8;
  }
}
static inline int lcp_len(const unsigned char *s, uint32_t i, uint32_t j) {
  const unsigned char *p = s + i, *q = s + j;
  int h = 0;
  for (;;) {
    uint64_t a; memcpy(&a, p, 8); a = __builtin_bswap64(a);
    uint64_t b; memcpy(&b, q, 8); b = __builtin_bswap64(b);
    if (a != b) return h + ((int)(__builtin_clzll(a ^ b) >> 3));
    h += 8; p += 8; q += 8;
  }
}

static int g_fallback = 0, g_maxrun = 0, g_maxbkt = 0;

static int solve_string(const unsigned char *q, long sn, char **opo) {
  build_map();
  while (sn > 0 && (*q == ' ' || *q == '\n' || *q == '\r' || *q == '\t')) { q++; sn--; }
  int n = 0;
  while (n < sn && q[n] != 0 && q[n] != ' ' && q[n] != '\n' && q[n] != '\r' && q[n] != '\t') {
    str[n] = q[n]; n++;
  }
  if (n <= 0) return 0;
  memset(str + n, 0, PADB);
  P2[0] = rd();
  plan_digits();
  uint32_t nb = msd_stage(str, AA, n);
  P2[1] = rd();
  gstart[nb] = (uint32_t)n;
  int bad = 0;
  for (uint32_t k = 0; k < nb; k++) {
    uint32_t m = gstart[k + 1] - gstart[k];
    if (m > (uint32_t)g_maxbkt) g_maxbkt = (int)m;
    if (bucket_sort_lsd(str, gstart[k], gstart[k + 1]) < 0) { bad = 1; break; }
  }
  P2[2] = rd();
  if (bad) {   // non-random data: SA-IS
    g_fallback = 1;
    sais<unsigned char>(str, sa_, n + 1, 256, 0);
    for (int x = 0; x < n; x++) sa_[x] = sa_[x + 1];
  } else {
    P2[3] = rd();
    // stage 3: refine runs + LCP in one pass
    uint32_t prev = AA[0];
    uint64_t kp = key48(str + prev);
    int i = 1;
    while (i < n) {
      uint32_t cur = AA[i];
      uint64_t kc = key48(str + cur);
      if (kc != kp) { lcp_[i] = (int)((__builtin_clzll(kc ^ kp) - 16) >> 3); i++; prev = cur; kp = kc; continue; }
      int j = i;
      while (j < n && key48(str + AA[j]) == kp) j++;
      if (j - i + 1 > g_maxrun) g_maxrun = j - i + 1;
      if (j - i + 1 > 64) { bad = 1; break; }
      for (int x = i; x < j; x++) {                // insertion sort inside the run [i-1, j)
        uint32_t v = AA[x];
        int y = x - 1;
        while (y >= i - 1 && suf_less(str, v, AA[y])) { AA[y + 1] = AA[y]; y--; }
        AA[y + 1] = v;
      }
      int a = i - 1, b = j;
      for (int x = (a >= 1 ? a : 1); x <= b && x < n; x++) lcp_[x] = lcp_len(str, AA[x - 1], AA[x]);
      prev = AA[j - 1];
      kp = key48(str + AA[j - 1]);
      i = j;
    }
    P2[4] = rd();
    if (bad) {
      g_fallback = 1;
      sais<unsigned char>(str, sa_, n + 1, 256, 0);
      for (int x = 0; x < n; x++) sa_[x] = sa_[x + 1];
    } else {
      for (int x = 0; x < n; x++) sa_[x] = (int)AA[x];
    }
  }
  if (g_fallback) for (int x = 0; x + 1 < n; x++) lcp_[x + 1] = lcp_len(str, (uint32_t)sa_[x], (uint32_t)sa_[x + 1]);
  P2[5] = rd();
  // output
  char *o = *opo;
  build_dig4();
  for (int x = 0; x < n - 1; x++) { o = putu(o, (unsigned)(sa_[x] + 1)); *o++ = ' '; }
  o = putu_exact(o, (unsigned)(sa_[n - 1] + 1)); *o++ = '\n';
  P2[6] = rd();
  for (int x = 1; x < n - 1; x++) { o = putu(o, (unsigned)lcp_[x]); *o++ = ' '; }
  o = putu_exact(o, (unsigned)lcp_[n - 1]); *o++ = '\n';
  P2[7] = rd();
  *opo = o;
  return 1;
}

#ifdef BENCH
#include <cstdio>
#include <cstdlib>
int main(int argc, char **argv) {
  int n = (argc > 1) ? atoi(argv[1]) : 1000000;
  unsigned long long seed = 123456789ULL;
  for (int i = 0; i < n; i++) {
    seed ^= seed << 13; seed ^= seed >> 7; seed ^= seed << 17;
    str[i] = (unsigned char)('a' + (seed % 26));
  }
  str[n] = 0;
  char *o = OUT;
  unsigned long long t0 = rd();
  solve_string(str, n, &o);
  unsigned long long t1 = rd();
  printf("n=%d msd=%llu bucketsort=%llu refine=%llu copysa=%llu outsa=%llu outlcp=%llu total=%llu maxrun=%d maxbkt=%d fb=%d nd=%d\n",
         n, P2[1] - P2[0], P2[2] - P2[1], P2[4] - P2[3], P2[5] - P2[4],
         P2[6] - P2[5], P2[7] - P2[6], t1 - t0, g_maxrun, g_maxbkt, g_fallback, g_nd);
  unsigned long long sum = 0; for (int i = 0; i < n; i++) sum = sum * 131 + (unsigned)sa_[i];
  for (int i = 1; i < n; i++) sum = sum * 131 + (unsigned)lcp_[i];
  unsigned long long oh = 1469598103934665603ULL; for (long i = 0; i < (long)(o - OUT); i++) oh = (oh ^ (unsigned char)OUT[i]) * 1099511628211ULL;
  printf("chk %llu olen %ld ohash %llu\n", sum, (long)(o - OUT), oh);
  return 0;
}
#elif defined(JUDGE)
struct DI {
  unsigned long abi;
  const char *s; unsigned long sn;
  char *o; unsigned long ol; unsigned long os;
  char *e; unsigned long el; unsigned long es;
  const char *IB; unsigned long IBl;
  char *OB; unsigned long OBl;
  unsigned long tsc;
} __attribute__((packed));
extern "C" void __libc_start_main(void *m, int argc, char **argv) {
  (void)m;
  unsigned long *p = (unsigned long *)(argv + argc + 1);
  while (*p) p++;
  p++;
  DI *d = 0;
  for (int i = 0; i < 32 && p[0]; i++, p += 2)
    if (p[0] == 0x6b637564UL) { d = (DI *)p[1]; break; }
  if (d) {
    char *o = d->o;
    if (solve_string((const unsigned char *)d->s, (long)d->sn, &o)) d->os = (unsigned long)(o - d->o);
  }
  __asm__ volatile("syscall" ::"a"(60), "D"(0) : "rcx", "r11", "memory");
  for (;;);
}
int main() { return 0; }
#endif

评测结果