代码

// 1006: suffix array + LCP, n <= 1e5, lowercase string.
// SA-IS with packed (char-type, L/S-flag) array to halve random accesses.
#include <cstdio>
#include <cstring>
#include <type_traits>
#include <sys/auxv.h>
typedef unsigned long long u64;
struct DI { u64 abi; const char *in; u64 insz; char *out; u64 outlim; u64 outsz; char *err;
            u64 errlim; u64 errsz; const char *IB; u64 IBlim; char *OB; u64 OBlim; u64 tscfreq; }
            __attribute__((packed));

static const int MAXN = 100005;
static int sa_[MAXN], rnk[MAXN], lcp[MAXN];

static int ARENA[1 << 21];
static int *asp = ARENA;
static inline int *alloc_ints(int cnt) { int *p = asp; asp += cnt; return p; }

template <class PT>
static void induce(const PT *p, int *sa, int n, const int *sum_l, const int *sum_s,
                   int upper, const int *src, int srclen, int *buf) {
    memset(sa, 0xff, sizeof(int) * (size_t)n);
    for (int i = 0; i <= upper; i++) buf[i] = sum_s[i];
    for (int i = 0; i < srclen; i++) { int d = src[i]; if (d == n) continue; sa[buf[p[d] >> 1]++] = d; }
    for (int i = 0; i <= upper; i++) buf[i] = sum_l[i];
    sa[buf[p[n - 1] >> 1]++] = n - 1;
    for (int i = 0; i < n; i++) {
        int v = sa[i];
        if (v >= 1) { PT t = p[v - 1]; if (!(t & 1)) sa[buf[t >> 1]++] = v - 1; }
    }
    for (int i = 0; i <= upper; i++) buf[i] = sum_l[i];
    for (int i = n - 1; i >= 0; i--) {
        int v = sa[i];
        if (v >= 1) { PT t = p[v - 1]; if (t & 1) sa[--buf[(t >> 1) + 1]] = v - 1; }
    }
}

template <class ST>
static void sa_is(const ST *s, int *sa, int n, int upper) {
    typedef typename std::conditional<sizeof(ST) == 1, unsigned char, unsigned int>::type PT;
    if (n == 1) { sa[0] = 0; return; }
    if (n == 2) { if (s[0] < s[1]) { sa[0] = 0; sa[1] = 1; } else { sa[0] = 1; sa[1] = 0; } return; }
    int *save = asp;
    PT *p = (PT *)alloc_ints(((n * (int)sizeof(PT) + 3) / 4) + 2);
    int *sum_l = alloc_ints(upper + 2);
    int *sum_s = alloc_ints(upper + 2);
    int *buf = alloc_ints(upper + 2);
    int *lms = alloc_ints(n / 2 + 2);
    int *lms_map = alloc_ints(n + 1);
    int *sorted_lms = alloc_ints(n / 2 + 2);
    int *rec_s = alloc_ints(n / 2 + 2);
    int *rec_sa = alloc_ints(n / 2 + 2);

    // ls bits
    p[n - 1] = (PT)((s[n - 1] << 1));
    int prev = 0;
    for (int i = n - 2; i >= 0; i--) {
        prev = (s[i] == s[i + 1]) ? prev : (s[i] < s[i + 1] ? 1 : 0);
        p[i] = (PT)((s[i] << 1) | prev);
    }
    for (int i = 0; i <= upper; i++) { sum_l[i] = 0; sum_s[i] = 0; }
    for (int i = 0; i < n; i++) {
        PT t = p[i];
        if (!(t & 1)) sum_s[t >> 1]++;
        else sum_l[(t >> 1) + 1]++;
    }
    for (int i = 0; i <= upper; i++) {
        sum_s[i] += sum_l[i];
        if (i < upper) sum_l[i + 1] += sum_s[i];
    }
    int m = 0;
    for (int i = 0; i <= n; i++) lms_map[i] = -1;
    for (int i = 1; i < n; i++) if (!(p[i - 1] & 1) && (p[i] & 1)) { lms_map[i] = m; lms[m++] = i; }

    induce(p, sa, n, sum_l, sum_s, upper, lms, m, buf);
    if (m == 0) { asp = save; return; }

    int cnt = 0;
    for (int i = 0; i < n; i++) if (sa[i] >= 0 && lms_map[sa[i]] != -1) sorted_lms[cnt++] = sa[i];
    int rec_upper = 0;
    rec_s[lms_map[sorted_lms[0]]] = 0;
    for (int i = 1; i < m; i++) {
        int l = sorted_lms[i - 1], r = sorted_lms[i];
        int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
        int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
        bool same = true;
        if (end_l - l != end_r - r) same = false;
        else {
            while (l < end_l) { if ((p[l] >> 1) != (p[r] >> 1)) break; l++; r++; }
            if (l == n || (p[l] >> 1) != (p[r] >> 1)) same = false;
        }
        if (!same) rec_upper++;
        rec_s[lms_map[sorted_lms[i]]] = rec_upper;
    }
    if (rec_upper + 1 == m) {
        for (int i = 0; i < m; i++) rec_sa[rec_s[i]] = i;
    } else {
        sa_is(rec_s, rec_sa, m, rec_upper);
    }
    for (int i = 0; i < m; i++) sorted_lms[i] = lms[rec_sa[i]];
    induce(p, sa, n, sum_l, sum_s, upper, sorted_lms, m, buf);
    asp = save;
}

static char outbuf[1 << 22];

static const char DIG[201] =
    "00010203040506070809" "10111213141516171819" "20212223242526272829"
    "30313233343536373839" "40414243444546474849" "50515253545556575859"
    "60616263646566676869" "70717273747576777879" "80818283848586878889"
    "90919293949596979899";

static inline char *writeInt(char *p, unsigned v) {
    if (v < 100) {
        if (v < 10) *p++ = char('0' + v);
        else { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
        return p;
    }
    unsigned r = v % 100; v /= 100;
    if (v < 100) {
        if (v < 10) *p++ = char('0' + v);
        else { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
        *p++ = DIG[2 * r]; *p++ = DIG[2 * r + 1];
        return p;
    }
    unsigned r2 = v % 100; v /= 100;
    if (v >= 10) { *p++ = DIG[2 * v]; *p++ = DIG[2 * v + 1]; }
    else *p++ = char('0' + v);
    *p++ = DIG[2 * r2]; *p++ = DIG[2 * r2 + 1];
    *p++ = DIG[2 * r]; *p++ = DIG[2 * r + 1];
    return p;
}

static char di_out_buf[1];
int main() {
    static unsigned char str[MAXN];
    int len = (int)fread(str, 1, MAXN - 2, stdin);
    while (len > 0 && (str[len - 1] == '\n' || str[len - 1] == '\r' || str[len - 1] == ' ')) len--;
    int n = len;
    static unsigned char s0[MAXN];
    s0[0] = 0;
    for (int i = 1; i <= n; i++) s0[i] = (unsigned char)(str[i - 1] - 'a' + 1);
    sa_is(s0, sa_, n + 1, 27);
    for (int i = 0; i < n; i++) sa_[i] = sa_[i + 1];
    for (int i = 0; i < n; i++) rnk[sa_[i]] = i;
    int k = 0;
    lcp[0] = 0;
    const int PF = 12;
    for (int i = 1; i <= n; i++) {
        if (i + PF <= n) __builtin_prefetch(&sa_[rnk[i + PF] + 1]);
        int r = rnk[i];
        if (r == n - 1) { k = 0; continue; }
        int j = sa_[r + 1];
        while (i + k <= n && j + k <= n && s0[i + k] == s0[j + k]) k++;
        lcp[r + 1] = k;
        if (k) k--;
    }
    DI *di = (DI *)getauxval(0x6b637564);
    char *obase = (di && di->out) ? di->out : outbuf;
    char *p = obase;
    for (int i = 0; i < n; i++) { if (i) *p++ = ' '; p = writeInt(p, sa_[i]); }
    *p++ = '\n';
    for (int i = 1; i < n; i++) { if (i > 1) *p++ = ' '; p = writeInt(p, lcp[i]); }
    *p++ = '\n';
    if (di && di->out) di->outsz = (u64)(p - obase);
    else fwrite(outbuf, 1, p - outbuf, stdout);
    return 0;
}

评测结果